bitmatch.ml

   1 (* Bitmatch library.
   2  * Copyright (C) 2008 Red Hat Inc., Richard W.M. Jones
   3  *
   4  * This library is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU Lesser General Public
   6  * License as published by the Free Software Foundation; either
   7  * version 2 of the License, or (at your option) any later version.
   8  *
   9  * This library is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12  * Lesser General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU Lesser General Public
  15  * License along with this library; if not, write to the Free Software
  16  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
  17  *
  18  * $Id: bitmatch.ml,v 1.14 2008-05-12 20:32:55 rjones Exp $
  19  *)
  20
  21 open Printf
  22
  23 (* Enable runtime debug messages.  Must also have been enabled
  24  * in pa_bitmatch.ml.
  25  *)
  26 let debug = ref false
  27
  28 (* Exceptions. *)
  29 exception Construct_failure of string * string * int * int
  30
  31 (* A bitstring is simply the data itself (as a string), and the
  32  * bitoffset and the bitlength within the string.  Note offset/length
  33  * are counted in bits, not bytes.
  34  *)
  35 type bitstring = string * int * int
  36
  37 (* Functions to create and load bitstrings. *)
  38 let empty_bitstring = "", 0, 0
  39
  40 let make_bitstring len c = String.make ((len+7) lsr 3) c, 0, len
  41
  42 let create_bitstring len = make_bitstring len '\000'
  43
  44 let bitstring_of_string str = str, 0, String.length str lsl 3
  45
  46 let bitstring_of_chan chan =
  47   let tmpsize = 16384 in
  48   let buf = Buffer.create tmpsize in
  49   let tmp = String.create tmpsize in
  50   let n = ref 0 in
  51   while n := input chan tmp 0 tmpsize; !n > 0 do
  52     Buffer.add_substring buf tmp 0 !n;
  53   done;
  54   Buffer.contents buf, 0, Buffer.length buf lsl 3
  55
  56 let bitstring_of_chan_max chan max =
  57   let tmpsize = 16384 in
  58   let buf = Buffer.create tmpsize in
  59   let tmp = String.create tmpsize in
  60   let len = ref 0 in
  61   let rec loop () =
  62     if !len < max then (
  63       let r = min tmpsize (max - !len) in
  64       let n = input chan tmp 0 r in
  65       if n > 0 then (
  66         Buffer.add_substring buf tmp 0 n;
  67         len := !len + n;
  68         loop ()
  69       )
  70     )
  71   in
  72   loop ();
  73   Buffer.contents buf, 0, !len lsl 3
  74
  75 let bitstring_of_file_descr fd =
  76   let tmpsize = 16384 in
  77   let buf = Buffer.create tmpsize in
  78   let tmp = String.create tmpsize in
  79   let n = ref 0 in
  80   while n := Unix.read fd tmp 0 tmpsize; !n > 0 do
  81     Buffer.add_substring buf tmp 0 !n;
  82   done;
  83   Buffer.contents buf, 0, Buffer.length buf lsl 3
  84
  85 let bitstring_of_file_descr_max fd max =
  86   let tmpsize = 16384 in
  87   let buf = Buffer.create tmpsize in
  88   let tmp = String.create tmpsize in
  89   let len = ref 0 in
  90   let rec loop () =
  91     if !len < max then (
  92       let r = min tmpsize (max - !len) in
  93       let n = Unix.read fd tmp 0 r in
  94       if n > 0 then (
  95         Buffer.add_substring buf tmp 0 n;
  96         len := !len + n;
  97         loop ()
  98       )
  99     )
 100   in
 101   loop ();
 102   Buffer.contents buf, 0, !len lsl 3
 103
 104 let bitstring_of_file fname =
 105   let chan = open_in_bin fname in
 106   let bs = bitstring_of_chan chan in
 107   close_in chan;
 108   bs
 109
 110 let bitstring_length (_, _, len) = len
 111
 112 (*----------------------------------------------------------------------*)
 113 (* Bitwise functions.
 114  *
 115  * We try to isolate all bitwise functions within these modules.
 116  *)
 117
 118 module I = struct
 119   (* Bitwise operations on ints.  Note that we assume int <= 31 bits. *)
 120   let (<<) = (lsl)
 121   let (>>) = (lsr)
 122   external to_int : int -> int = "%identity"
 123   let zero = 0
 124   let one = 1
 125   let minus_one = -1
 126   let ff = 0xff
 127
 128   (* Create a mask so many bits wide. *)
 129   let mask bits =
 130     if bits < 30 then
 131       pred (one << bits)
 132     else if bits = 30 then
 133       max_int
 134     else if bits = 31 then
 135       minus_one
 136     else
 137       invalid_arg "Bitmatch.I.mask"
 138
 139   (* Byte swap an int of a given size. *)
 140   let byteswap v bits =
 141     if bits <= 8 then v
 142     else if bits <= 16 then (
 143       let shift = bits-8 in
 144       let v1 = v >> shift in
 145       let v2 = (v land (mask shift)) << 8 in
 146       v2 lor v1
 147     ) else if bits <= 24 then (
 148       let shift = bits - 16 in
 149       let v1 = v >> (8+shift) in
 150       let v2 = ((v >> shift) land ff) << 8 in
 151       let v3 = (v land (mask shift)) << 16 in
 152       v3 lor v2 lor v1
 153     ) else (
 154       let shift = bits - 24 in
 155       let v1 = v >> (16+shift) in
 156       let v2 = ((v >> (8+shift)) land ff) << 8 in
 157       let v3 = ((v >> shift) land ff) << 16 in
 158       let v4 = (v land (mask shift)) << 24 in
 159       v4 lor v3 lor v2 lor v1
 160     )
 161
 162   (* Check a value is in range 0 .. 2^bits-1. *)
 163   let range_unsigned v bits =
 164     let mask = lnot (mask bits) in
 165     (v land mask) = zero
 166
 167   (* Call function g on the top bits, then f on each full byte
 168    * (big endian - so start at top).
 169    *)
 170   let rec map_bytes_be g f v bits =
 171     if bits >= 8 then (
 172       map_bytes_be g f (v >> 8) (bits-8);
 173       let lsb = v land ff in
 174       f (to_int lsb)
 175     ) else if bits > 0 then (
 176       let lsb = v land (mask bits) in
 177       g (to_int lsb) bits
 178     )
 179 end
 180
 181 module I32 = struct
 182   (* Bitwise operations on int32s.  Note we try to keep it as similar
 183    * as possible to the I module above, to make it easier to track
 184    * down bugs.
 185    *)
 186   let (<<) = Int32.shift_left
 187   let (>>) = Int32.shift_right_logical
 188   let (land) = Int32.logand
 189   let (lor) = Int32.logor
 190   let lnot = Int32.lognot
 191   let pred = Int32.pred
 192   let max_int = Int32.max_int
 193   let to_int = Int32.to_int
 194   let zero = Int32.zero
 195   let one = Int32.one
 196   let minus_one = Int32.minus_one
 197   let ff = 0xff_l
 198
 199   (* Create a mask so many bits wide. *)
 200   let mask bits =
 201     if bits < 31 then
 202       pred (one << bits)
 203     else if bits = 31 then
 204       max_int
 205     else if bits = 32 then
 206       minus_one
 207     else
 208       invalid_arg "Bitmatch.I32.mask"
 209
 210   (* Byte swap an int of a given size. *)
 211   let byteswap v bits =
 212     if bits <= 8 then v
 213     else if bits <= 16 then (
 214       let shift = bits-8 in
 215       let v1 = v >> shift in
 216       let v2 = (v land (mask shift)) << 8 in
 217       v2 lor v1
 218     ) else if bits <= 24 then (
 219       let shift = bits - 16 in
 220       let v1 = v >> (8+shift) in
 221       let v2 = ((v >> shift) land ff) << 8 in
 222       let v3 = (v land (mask shift)) << 16 in
 223       v3 lor v2 lor v1
 224     ) else (
 225       let shift = bits - 24 in
 226       let v1 = v >> (16+shift) in
 227       let v2 = ((v >> (8+shift)) land ff) << 8 in
 228       let v3 = ((v >> shift) land ff) << 16 in
 229       let v4 = (v land (mask shift)) << 24 in
 230       v4 lor v3 lor v2 lor v1
 231     )
 232
 233   (* Check a value is in range 0 .. 2^bits-1. *)
 234   let range_unsigned v bits =
 235     let mask = lnot (mask bits) in
 236     (v land mask) = zero
 237
 238   (* Call function g on the top bits, then f on each full byte
 239    * (big endian - so start at top).
 240    *)
 241   let rec map_bytes_be g f v bits =
 242     if bits >= 8 then (
 243       map_bytes_be g f (v >> 8) (bits-8);
 244       let lsb = v land ff in
 245       f (to_int lsb)
 246     ) else if bits > 0 then (
 247       let lsb = v land (mask bits) in
 248       g (to_int lsb) bits
 249     )
 250 end
 251
 252 module I64 = struct
 253   (* Bitwise operations on int64s.  Note we try to keep it as similar
 254    * as possible to the I/I32 modules above, to make it easier to track
 255    * down bugs.
 256    *)
 257   let (<<) = Int64.shift_left
 258   let (>>) = Int64.shift_right_logical
 259   let (land) = Int64.logand
 260   let (lor) = Int64.logor
 261   let lnot = Int64.lognot
 262   let pred = Int64.pred
 263   let max_int = Int64.max_int
 264   let to_int = Int64.to_int
 265   let zero = Int64.zero
 266   let one = Int64.one
 267   let minus_one = Int64.minus_one
 268   let ff = 0xff_L
 269
 270   (* Create a mask so many bits wide. *)
 271   let mask bits =
 272     if bits < 63 then
 273       pred (one << bits)
 274     else if bits = 63 then
 275       max_int
 276     else if bits = 64 then
 277       minus_one
 278     else
 279       invalid_arg "Bitmatch.I64.mask"
 280
 281   (* Byte swap an int of a given size. *)
 282   (* let byteswap v bits = *)
 283
 284   (* Check a value is in range 0 .. 2^bits-1. *)
 285   let range_unsigned v bits =
 286     let mask = lnot (mask bits) in
 287     (v land mask) = zero
 288
 289   (* Call function g on the top bits, then f on each full byte
 290    * (big endian - so start at top).
 291    *)
 292   let rec map_bytes_be g f v bits =
 293     if bits >= 8 then (
 294       map_bytes_be g f (v >> 8) (bits-8);
 295       let lsb = v land ff in
 296       f (to_int lsb)
 297     ) else if bits > 0 then (
 298       let lsb = v land (mask bits) in
 299       g (to_int lsb) bits
 300     )
 301 end
 302
 303 (*----------------------------------------------------------------------*)
 304 (* Extraction functions.
 305  *
 306  * NB: internal functions, called from the generated macros, and
 307  * the parameters should have been checked for sanity already).
 308  *)
 309
 310 (* Bitstrings. *)
 311 let extract_bitstring data off len flen =
 312   (data, off, flen), off+flen, len-flen
 313
 314 let extract_remainder data off len =
 315   (data, off, len), off+len, 0
 316
 317 (* Extract and convert to numeric.  A single bit is returned as
 318  * a boolean.  There are no endianness or signedness considerations.
 319  *)
 320 let extract_bit data off len _ =        (* final param is always 1 *)
 321   let byteoff = off lsr 3 in
 322   let bitmask = 1 lsl (7 - (off land 7)) in
 323   let b = Char.code data.[byteoff] land bitmask <> 0 in
 324   b, off+1, len-1
 325
 326 (* Returns 8 bit unsigned aligned bytes from the string.
 327  * If the string ends then this returns 0's.
 328  *)
 329 let _get_byte data byteoff strlen =
 330   if strlen > byteoff then Char.code data.[byteoff] else 0
 331 let _get_byte32 data byteoff strlen =
 332   if strlen > byteoff then Int32.of_int (Char.code data.[byteoff]) else 0l
 333 let _get_byte64 data byteoff strlen =
 334   if strlen > byteoff then Int64.of_int (Char.code data.[byteoff]) else 0L
 335
 336 (* Extract [2..8] bits.  Because the result fits into a single
 337  * byte we don't have to worry about endianness, only signedness.
 338  *)
 339 let extract_char_unsigned data off len flen =
 340   let byteoff = off lsr 3 in
 341
 342   (* Optimize the common (byte-aligned) case. *)
 343   if off land 7 = 0 then (
 344     let byte = Char.code data.[byteoff] in
 345     byte lsr (8 - flen), off+flen, len-flen
 346   ) else (
 347     (* Extract the 16 bits at byteoff and byteoff+1 (note that the
 348      * second byte might not exist in the original string).
 349      *)
 350     let strlen = String.length data in
 351
 352     let word =
 353       (_get_byte data byteoff strlen lsl 8) +
 354         _get_byte data (byteoff+1) strlen in
 355
 356     (* Mask off the top bits. *)
 357     let bitmask = (1 lsl (16 - (off land 7))) - 1 in
 358     let word = word land bitmask in
 359     (* Shift right to get rid of the bottom bits. *)
 360     let shift = 16 - ((off land 7) + flen) in
 361     let word = word lsr shift in
 362
 363     word, off+flen, len-flen
 364   )
 365
 366 (* Extract [9..31] bits.  We have to consider endianness and signedness. *)
 367 let extract_int_be_unsigned data off len flen =
 368   let byteoff = off lsr 3 in
 369
 370   let strlen = String.length data in
 371
 372   let word =
 373     (* Optimize the common (byte-aligned) case. *)
 374     if off land 7 = 0 then (
 375       let word =
 376         (_get_byte data byteoff strlen lsl 23) +
 377           (_get_byte data (byteoff+1) strlen lsl 15) +
 378           (_get_byte data (byteoff+2) strlen lsl 7) +
 379           (_get_byte data (byteoff+3) strlen lsr 1) in
 380       word lsr (31 - flen)
 381     ) else if flen <= 24 then (
 382       (* Extract the 31 bits at byteoff .. byteoff+3. *)
 383       let word =
 384         (_get_byte data byteoff strlen lsl 23) +
 385           (_get_byte data (byteoff+1) strlen lsl 15) +
 386           (_get_byte data (byteoff+2) strlen lsl 7) +
 387           (_get_byte data (byteoff+3) strlen lsr 1) in
 388       (* Mask off the top bits. *)
 389       let bitmask = (1 lsl (31 - (off land 7))) - 1 in
 390       let word = word land bitmask in
 391       (* Shift right to get rid of the bottom bits. *)
 392       let shift = 31 - ((off land 7) + flen) in
 393       word lsr shift
 394     ) else (
 395       (* Extract the next 31 bits, slow method. *)
 396       let word =
 397         let c0, off, len = extract_char_unsigned data off len 8 in
 398         let c1, off, len = extract_char_unsigned data off len 8 in
 399         let c2, off, len = extract_char_unsigned data off len 8 in
 400         let c3, off, len = extract_char_unsigned data off len 7 in
 401         (c0 lsl 23) + (c1 lsl 15) + (c2 lsl 7) + c3 in
 402       word lsr (31 - flen)
 403     ) in
 404   word, off+flen, len-flen
 405
 406 let extract_int_le_unsigned data off len flen =
 407   let v, off, len = extract_int_be_unsigned data off len flen in
 408   let v = I.byteswap v flen in
 409   v, off, len
 410
 411 let _make_int32_be c0 c1 c2 c3 =
 412   Int32.logor
 413     (Int32.logor
 414        (Int32.logor
 415           (Int32.shift_left c0 24)
 416           (Int32.shift_left c1 16))
 417        (Int32.shift_left c2 8))
 418     c3
 419
 420 let _make_int32_le c0 c1 c2 c3 =
 421   Int32.logor
 422     (Int32.logor
 423        (Int32.logor
 424           (Int32.shift_left c3 24)
 425           (Int32.shift_left c2 16))
 426        (Int32.shift_left c1 8))
 427     c0
 428
 429 (* Extract exactly 32 bits.  We have to consider endianness and signedness. *)
 430 let extract_int32_be_unsigned data off len flen =
 431   let byteoff = off lsr 3 in
 432
 433   let strlen = String.length data in
 434
 435   let word =
 436     (* Optimize the common (byte-aligned) case. *)
 437     if off land 7 = 0 then (
 438       let word =
 439         let c0 = _get_byte32 data byteoff strlen in
 440         let c1 = _get_byte32 data (byteoff+1) strlen in
 441         let c2 = _get_byte32 data (byteoff+2) strlen in
 442         let c3 = _get_byte32 data (byteoff+3) strlen in
 443         _make_int32_be c0 c1 c2 c3 in
 444       Int32.shift_right_logical word (32 - flen)
 445     ) else (
 446       (* Extract the next 32 bits, slow method. *)
 447       let word =
 448         let c0, off, len = extract_char_unsigned data off len 8 in
 449         let c1, off, len = extract_char_unsigned data off len 8 in
 450         let c2, off, len = extract_char_unsigned data off len 8 in
 451         let c3, _, _ = extract_char_unsigned data off len 8 in
 452         let c0 = Int32.of_int c0 in
 453         let c1 = Int32.of_int c1 in
 454         let c2 = Int32.of_int c2 in
 455         let c3 = Int32.of_int c3 in
 456         _make_int32_be c0 c1 c2 c3 in
 457       Int32.shift_right_logical word (32 - flen)
 458     ) in
 459   word, off+flen, len-flen
 460
 461 let extract_int32_le_unsigned data off len flen =
 462   let v, off, len = extract_int32_be_unsigned data off len flen in
 463   let v = I32.byteswap v flen in
 464   v, off, len
 465
 466 let _make_int64_be c0 c1 c2 c3 c4 c5 c6 c7 =
 467   Int64.logor
 468     (Int64.logor
 469        (Int64.logor
 470           (Int64.logor
 471              (Int64.logor
 472                 (Int64.logor
 473                    (Int64.logor
 474                       (Int64.shift_left c0 56)
 475                       (Int64.shift_left c1 48))
 476                    (Int64.shift_left c2 40))
 477                 (Int64.shift_left c3 32))
 478              (Int64.shift_left c4 24))
 479           (Int64.shift_left c5 16))
 480        (Int64.shift_left c6 8))
 481     c7
 482
 483 let _make_int64_le c0 c1 c2 c3 c4 c5 c6 c7 =
 484   _make_int64_be c7 c6 c5 c4 c3 c2 c1 c0
 485
 486 (* Extract [1..64] bits.  We have to consider endianness and signedness. *)
 487 let extract_int64_be_unsigned data off len flen =
 488   let byteoff = off lsr 3 in
 489
 490   let strlen = String.length data in
 491
 492   let word =
 493     (* Optimize the common (byte-aligned) case. *)
 494     if off land 7 = 0 then (
 495       let word =
 496         let c0 = _get_byte64 data byteoff strlen in
 497         let c1 = _get_byte64 data (byteoff+1) strlen in
 498         let c2 = _get_byte64 data (byteoff+2) strlen in
 499         let c3 = _get_byte64 data (byteoff+3) strlen in
 500         let c4 = _get_byte64 data (byteoff+4) strlen in
 501         let c5 = _get_byte64 data (byteoff+5) strlen in
 502         let c6 = _get_byte64 data (byteoff+6) strlen in
 503         let c7 = _get_byte64 data (byteoff+7) strlen in
 504         _make_int64_be c0 c1 c2 c3 c4 c5 c6 c7 in
 505       Int64.shift_right_logical word (64 - flen)
 506     ) else (
 507       (* Extract the next 64 bits, slow method. *)
 508       let word =
 509         let c0, off, len = extract_char_unsigned data off len 8 in
 510         let c1, off, len = extract_char_unsigned data off len 8 in
 511         let c2, off, len = extract_char_unsigned data off len 8 in
 512         let c3, off, len = extract_char_unsigned data off len 8 in
 513         let c4, off, len = extract_char_unsigned data off len 8 in
 514         let c5, off, len = extract_char_unsigned data off len 8 in
 515         let c6, off, len = extract_char_unsigned data off len 8 in
 516         let c7, _, _ = extract_char_unsigned data off len 8 in
 517         let c0 = Int64.of_int c0 in
 518         let c1 = Int64.of_int c1 in
 519         let c2 = Int64.of_int c2 in
 520         let c3 = Int64.of_int c3 in
 521         let c4 = Int64.of_int c4 in
 522         let c5 = Int64.of_int c5 in
 523         let c6 = Int64.of_int c6 in
 524         let c7 = Int64.of_int c7 in
 525         _make_int64_be c0 c1 c2 c3 c4 c5 c6 c7 in
 526       Int64.shift_right_logical word (64 - flen)
 527     ) in
 528   word, off+flen, len-flen
 529
 530 let extract_int64_le_unsigned data off len flen =
 531   let byteoff = off lsr 3 in
 532
 533   let strlen = String.length data in
 534
 535   let word =
 536     (* Optimize the common (byte-aligned) case. *)
 537     if off land 7 = 0 then (
 538       let word =
 539         let c0 = _get_byte64 data byteoff strlen in
 540         let c1 = _get_byte64 data (byteoff+1) strlen in
 541         let c2 = _get_byte64 data (byteoff+2) strlen in
 542         let c3 = _get_byte64 data (byteoff+3) strlen in
 543         let c4 = _get_byte64 data (byteoff+4) strlen in
 544         let c5 = _get_byte64 data (byteoff+5) strlen in
 545         let c6 = _get_byte64 data (byteoff+6) strlen in
 546         let c7 = _get_byte64 data (byteoff+7) strlen in
 547         _make_int64_le c0 c1 c2 c3 c4 c5 c6 c7 in
 548       Int64.logand word (I64.mask flen)
 549     ) else (
 550       (* Extract the next 64 bits, slow method. *)
 551       let word =
 552         let c0, off, len = extract_char_unsigned data off len 8 in
 553         let c1, off, len = extract_char_unsigned data off len 8 in
 554         let c2, off, len = extract_char_unsigned data off len 8 in
 555         let c3, off, len = extract_char_unsigned data off len 8 in
 556         let c4, off, len = extract_char_unsigned data off len 8 in
 557         let c5, off, len = extract_char_unsigned data off len 8 in
 558         let c6, off, len = extract_char_unsigned data off len 8 in
 559         let c7, _, _ = extract_char_unsigned data off len 8 in
 560         let c0 = Int64.of_int c0 in
 561         let c1 = Int64.of_int c1 in
 562         let c2 = Int64.of_int c2 in
 563         let c3 = Int64.of_int c3 in
 564         let c4 = Int64.of_int c4 in
 565         let c5 = Int64.of_int c5 in
 566         let c6 = Int64.of_int c6 in
 567         let c7 = Int64.of_int c7 in
 568         _make_int64_le c0 c1 c2 c3 c4 c5 c6 c7 in
 569       Int64.logand word (I64.mask flen)
 570     ) in
 571   word, off+flen, len-flen
 572
 573 (*----------------------------------------------------------------------*)
 574 (* Constructor functions. *)
 575
 576 module Buffer = struct
 577   type t = {
 578     buf : Buffer.t;
 579     mutable len : int;                  (* Length in bits. *)
 580     (* Last byte in the buffer (if len is not aligned).  We store
 581      * it outside the buffer because buffers aren't mutable.
 582      *)
 583     mutable last : int;
 584   }
 585
 586   let create () =
 587     (* XXX We have almost enough information in the generator to
 588      * choose a good initial size.
 589      *)
 590     { buf = Buffer.create 128; len = 0; last = 0 }
 591
 592   let contents { buf = buf; len = len; last = last } =
 593     let data =
 594       if len land 7 = 0 then
 595         Buffer.contents buf
 596       else
 597         Buffer.contents buf ^ (String.make 1 (Char.chr last)) in
 598     data, 0, len
 599
 600   (* Add exactly 8 bits. *)
 601   let add_byte ({ buf = buf; len = len; last = last } as t) byte =
 602     if byte < 0 || byte > 255 then invalid_arg "Bitmatch.Buffer.add_byte";
 603     let shift = len land 7 in
 604     if shift = 0 then
 605       (* Target buffer is byte-aligned. *)
 606       Buffer.add_char buf (Char.chr byte)
 607     else (
 608       (* Target buffer is unaligned.  'last' is meaningful. *)
 609       let first = byte lsr shift in
 610       let second = (byte lsl (8 - shift)) land 0xff in
 611       Buffer.add_char buf (Char.chr (last lor first));
 612       t.last <- second
 613     );
 614     t.len <- t.len + 8
 615
 616   (* Add exactly 1 bit. *)
 617   let add_bit ({ buf = buf; len = len; last = last } as t) bit =
 618     let shift = 7 - (len land 7) in
 619     if shift > 0 then
 620       (* Somewhere in the middle of 'last'. *)
 621       t.last <- last lor ((if bit then 1 else 0) lsl shift)
 622     else (
 623       (* Just a single spare bit in 'last'. *)
 624       let last = last lor if bit then 1 else 0 in
 625       Buffer.add_char buf (Char.chr last);
 626       t.last <- 0
 627     );
 628     t.len <- len + 1
 629
 630   (* Add a small number of bits (definitely < 8).  This uses a loop
 631    * to call add_bit so it's slow.
 632    *)
 633   let _add_bits t c slen =
 634     if slen < 1 || slen >= 8 then invalid_arg "Bitmatch.Buffer._add_bits";
 635     for i = slen-1 downto 0 do
 636       let bit = c land (1 lsl i) <> 0 in
 637       add_bit t bit
 638     done
 639
 640   let add_bits ({ buf = buf; len = len } as t) str slen =
 641     if slen > 0 then (
 642       if len land 7 = 0 then (
 643         if slen land 7 = 0 then
 644           (* Common case - everything is byte-aligned. *)
 645           Buffer.add_substring buf str 0 (slen lsr 3)
 646         else (
 647           (* Target buffer is aligned.  Copy whole bytes then leave the
 648            * remaining bits in last.
 649            *)
 650           let slenbytes = slen lsr 3 in
 651           if slenbytes > 0 then Buffer.add_substring buf str 0 slenbytes;
 652           t.last <- Char.code str.[slenbytes] lsl (8 - (slen land 7))
 653         );
 654         t.len <- len + slen
 655       ) else (
 656         (* Target buffer is unaligned.  Copy whole bytes using
 657          * add_byte which knows how to deal with an unaligned
 658          * target buffer, then call _add_bits for the remaining < 8 bits.
 659          *
 660          * XXX This is going to be dog-slow.
 661          *)
 662         let slenbytes = slen lsr 3 in
 663         for i = 0 to slenbytes-1 do
 664           let byte = Char.code str.[i] in
 665           add_byte t byte
 666         done;
 667         _add_bits t (Char.code str.[slenbytes]) (slen - (slenbytes lsl 3))
 668       );
 669     )
 670 end
 671
 672 (* Construct a single bit. *)
 673 let construct_bit buf b _ _ =
 674   Buffer.add_bit buf b
 675
 676 (* Construct a field, flen = [2..8]. *)
 677 let construct_char_unsigned buf v flen exn =
 678   let max_val = 1 lsl flen in
 679   if v < 0 || v >= max_val then raise exn;
 680   if flen = 8 then
 681     Buffer.add_byte buf v
 682   else
 683     Buffer._add_bits buf v flen
 684
 685 (* Construct a field of up to 31 bits. *)
 686 let construct_int_be_unsigned buf v flen exn =
 687   (* Check value is within range. *)
 688   if not (I.range_unsigned v flen) then raise exn;
 689   (* Add the bytes. *)
 690   I.map_bytes_be (Buffer._add_bits buf) (Buffer.add_byte buf) v flen
 691
 692 (* Construct a field of exactly 32 bits. *)
 693 let construct_int32_be_unsigned buf v flen _ =
 694   Buffer.add_byte buf
 695     (Int32.to_int (Int32.shift_right_logical v 24));
 696   Buffer.add_byte buf
 697     (Int32.to_int ((Int32.logand (Int32.shift_right_logical v 16) 0xff_l)));
 698   Buffer.add_byte buf
 699     (Int32.to_int ((Int32.logand (Int32.shift_right_logical v 8) 0xff_l)));
 700   Buffer.add_byte buf
 701     (Int32.to_int (Int32.logand v 0xff_l))
 702
 703 (* Construct a field of up to 64 bits. *)
 704 let construct_int64_be_unsigned buf v flen exn =
 705   (* Check value is within range. *)
 706   if not (I64.range_unsigned v flen) then raise exn;
 707   (* Add the bytes. *)
 708   I64.map_bytes_be (Buffer._add_bits buf) (Buffer.add_byte buf) v flen
 709
 710 (* Construct from a string of bytes, exact multiple of 8 bits
 711  * in length of course.
 712  *)
 713 let construct_string buf str =
 714   let len = String.length str in
 715   Buffer.add_bits buf str (len lsl 3)
 716
 717 (*----------------------------------------------------------------------*)
 718 (* Extract a string from a bitstring. *)
 719
 720 let string_of_bitstring (data, off, len) =
 721   if off land 7 = 0 && len land 7 = 0 then
 722     (* Easy case: everything is byte-aligned. *)
 723     String.sub data (off lsr 3) (len lsr 3)
 724   else (
 725     (* Bit-twiddling case. *)
 726     let strlen = (len + 7) lsr 3 in
 727     let str = String.make strlen '\000' in
 728     let rec loop data off len i =
 729       if len >= 8 then (
 730         let c, off, len = extract_char_unsigned data off len 8 in
 731         str.[i] <- Char.chr c;
 732         loop data off len (i+1)
 733       ) else if len > 0 then (
 734         let c, off, len = extract_char_unsigned data off len len in
 735         str.[i] <- Char.chr c
 736       )
 737     in
 738     loop data off len 0;
 739     str
 740   )
 741
 742 (*----------------------------------------------------------------------*)
 743 (* Display functions. *)
 744
 745 let isprint c =
 746   let c = Char.code c in
 747   c >= 32 && c < 127
 748
 749 let hexdump_bitstring chan (data, off, len) =
 750   let count = ref 0 in
 751   let off = ref off in
 752   let len = ref len in
 753   let linelen = ref 0 in
 754   let linechars = String.make 16 ' ' in
 755
 756   fprintf chan "00000000  ";
 757
 758   while !len > 0 do
 759     let bits = min !len 8 in
 760     let byte, off', len' = extract_char_unsigned data !off !len bits in
 761     off := off'; len := len';
 762
 763     let byte = byte lsl (8-bits) in
 764     fprintf chan "%02x " byte;
 765
 766     incr count;
 767     linechars.[!linelen] <-
 768       (let c = Char.chr byte in
 769        if isprint c then c else '.');
 770     incr linelen;
 771     if !linelen = 8 then fprintf chan " ";
 772     if !linelen = 16 then (
 773       fprintf chan " |%s|\n%08x  " linechars !count;
 774       linelen := 0;
 775       for i = 0 to 15 do linechars.[i] <- ' ' done
 776     )
 777   done;
 778
 779   if !linelen > 0 then (
 780     let skip = (16 - !linelen) * 3 + if !linelen < 8 then 1 else 0 in
 781     for i = 0 to skip-1 do fprintf chan " " done;
 782     fprintf chan " |%s|\n%!" linechars
 783   ) else
 784     fprintf chan "\n%!"