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.9 2008-04-15 13:40:51 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_chan chan =
  45   let tmpsize = 16384 in
  46   let buf = Buffer.create tmpsize in
  47   let tmp = String.create tmpsize in
  48   let n = ref 0 in
  49   while n := input chan tmp 0 tmpsize; !n > 0 do
  50     Buffer.add_substring buf tmp 0 !n;
  51   done;
  52   Buffer.contents buf, 0, Buffer.length buf lsl 3
  53
  54 let bitstring_of_file fname =
  55   let chan = open_in_bin fname in
  56   let bs = bitstring_of_chan chan in
  57   close_in chan;
  58   bs
  59
  60 let bitstring_length (_, _, len) = len
  61
  62 (*----------------------------------------------------------------------*)
  63 (* Bitwise functions.
  64  *
  65  * We try to isolate all bitwise functions within these modules.
  66  *)
  67
  68 module I = struct
  69   (* Bitwise operations on ints.  Note that we assume int <= 31 bits. *)
  70   let (<<) = (lsl)
  71   let (>>) = (lsr)
  72   external to_int : int -> int = "%identity"
  73   let zero = 0
  74   let one = 1
  75   let minus_one = -1
  76   let ff = 0xff
  77
  78   (* Create a mask so many bits wide. *)
  79   let mask bits =
  80     if bits < 30 then
  81       pred (one << bits)
  82     else if bits = 30 then
  83       max_int
  84     else if bits = 31 then
  85       minus_one
  86     else
  87       invalid_arg "Bitmatch.I.mask"
  88
  89   (* Byte swap an int of a given size. *)
  90   let byteswap v bits =
  91     if bits <= 8 then v
  92     else if bits <= 16 then (
  93       let shift = bits-8 in
  94       let v1 = v >> shift in
  95       let v2 = (v land (mask shift)) << 8 in
  96       v2 lor v1
  97     ) else if bits <= 24 then (
  98       let shift = bits - 16 in
  99       let v1 = v >> (8+shift) in
 100       let v2 = ((v >> shift) land ff) << 8 in
 101       let v3 = (v land (mask shift)) << 16 in
 102       v3 lor v2 lor v1
 103     ) else (
 104       let shift = bits - 24 in
 105       let v1 = v >> (16+shift) in
 106       let v2 = ((v >> (8+shift)) land ff) << 8 in
 107       let v3 = ((v >> shift) land ff) << 16 in
 108       let v4 = (v land (mask shift)) << 24 in
 109       v4 lor v3 lor v2 lor v1
 110     )
 111
 112   (* Check a value is in range 0 .. 2^bits-1. *)
 113   let range_unsigned v bits =
 114     let mask = lnot (mask bits) in
 115     (v land mask) = zero
 116
 117   (* Call function g on the top bits, then f on each full byte
 118    * (big endian - so start at top).
 119    *)
 120   let rec map_bytes_be g f v bits =
 121     if bits >= 8 then (
 122       map_bytes_be g f (v >> 8) (bits-8);
 123       let lsb = v land ff in
 124       f (to_int lsb)
 125     ) else if bits > 0 then (
 126       let lsb = v land (mask bits) in
 127       g (to_int lsb) bits
 128     )
 129 end
 130
 131 module I32 = struct
 132   (* Bitwise operations on int32s.  Note we try to keep it as similar
 133    * as possible to the I module above, to make it easier to track
 134    * down bugs.
 135    *)
 136   let (<<) = Int32.shift_left
 137   let (>>) = Int32.shift_right_logical
 138   let (land) = Int32.logand
 139   let (lor) = Int32.logor
 140   let lnot = Int32.lognot
 141   let pred = Int32.pred
 142   let max_int = Int32.max_int
 143   let to_int = Int32.to_int
 144   let zero = Int32.zero
 145   let one = Int32.one
 146   let minus_one = Int32.minus_one
 147   let ff = 0xff_l
 148
 149   (* Create a mask so many bits wide. *)
 150   let mask bits =
 151     if bits < 31 then
 152       pred (one << bits)
 153     else if bits = 31 then
 154       max_int
 155     else if bits = 32 then
 156       minus_one
 157     else
 158       invalid_arg "Bitmatch.I32.mask"
 159
 160   (* Byte swap an int of a given size. *)
 161   let byteswap v bits =
 162     if bits <= 8 then v
 163     else if bits <= 16 then (
 164       let shift = bits-8 in
 165       let v1 = v >> shift in
 166       let v2 = (v land (mask shift)) << 8 in
 167       v2 lor v1
 168     ) else if bits <= 24 then (
 169       let shift = bits - 16 in
 170       let v1 = v >> (8+shift) in
 171       let v2 = ((v >> shift) land ff) << 8 in
 172       let v3 = (v land (mask shift)) << 16 in
 173       v3 lor v2 lor v1
 174     ) else (
 175       let shift = bits - 24 in
 176       let v1 = v >> (16+shift) in
 177       let v2 = ((v >> (8+shift)) land ff) << 8 in
 178       let v3 = ((v >> shift) land ff) << 16 in
 179       let v4 = (v land (mask shift)) << 24 in
 180       v4 lor v3 lor v2 lor v1
 181     )
 182
 183   (* Check a value is in range 0 .. 2^bits-1. *)
 184   let range_unsigned v bits =
 185     let mask = lnot (mask bits) in
 186     (v land mask) = zero
 187
 188   (* Call function g on the top bits, then f on each full byte
 189    * (big endian - so start at top).
 190    *)
 191   let rec map_bytes_be g f v bits =
 192     if bits >= 8 then (
 193       map_bytes_be g f (v >> 8) (bits-8);
 194       let lsb = v land ff in
 195       f (to_int lsb)
 196     ) else if bits > 0 then (
 197       let lsb = v land (mask bits) in
 198       g (to_int lsb) bits
 199     )
 200 end
 201
 202 module I64 = struct
 203   (* Bitwise operations on int64s.  Note we try to keep it as similar
 204    * as possible to the I/I32 modules above, to make it easier to track
 205    * down bugs.
 206    *)
 207   let (<<) = Int64.shift_left
 208   let (>>) = Int64.shift_right_logical
 209   let (land) = Int64.logand
 210   let (lor) = Int64.logor
 211   let lnot = Int64.lognot
 212   let pred = Int64.pred
 213   let max_int = Int64.max_int
 214   let to_int = Int64.to_int
 215   let zero = Int64.zero
 216   let one = Int64.one
 217   let minus_one = Int64.minus_one
 218   let ff = 0xff_L
 219
 220   (* Create a mask so many bits wide. *)
 221   let mask bits =
 222     if bits < 63 then
 223       pred (one << bits)
 224     else if bits = 63 then
 225       max_int
 226     else if bits = 64 then
 227       minus_one
 228     else
 229       invalid_arg "Bitmatch.I64.mask"
 230
 231   (* Byte swap an int of a given size. *)
 232   (* let byteswap v bits = *)
 233
 234   (* Check a value is in range 0 .. 2^bits-1. *)
 235   let range_unsigned v bits =
 236     let mask = lnot (mask bits) in
 237     (v land mask) = zero
 238
 239   (* Call function g on the top bits, then f on each full byte
 240    * (big endian - so start at top).
 241    *)
 242   let rec map_bytes_be g f v bits =
 243     if bits >= 8 then (
 244       map_bytes_be g f (v >> 8) (bits-8);
 245       let lsb = v land ff in
 246       f (to_int lsb)
 247     ) else if bits > 0 then (
 248       let lsb = v land (mask bits) in
 249       g (to_int lsb) bits
 250     )
 251 end
 252
 253 (*----------------------------------------------------------------------*)
 254 (* Extraction functions.
 255  *
 256  * NB: internal functions, called from the generated macros, and
 257  * the parameters should have been checked for sanity already).
 258  *)
 259
 260 (* Bitstrings. *)
 261 let extract_bitstring data off len flen =
 262   (data, off, flen), off+flen, len-flen
 263
 264 let extract_remainder data off len =
 265   (data, off, len), off+len, 0
 266
 267 (* Extract and convert to numeric.  A single bit is returned as
 268  * a boolean.  There are no endianness or signedness considerations.
 269  *)
 270 let extract_bit data off len _ =        (* final param is always 1 *)
 271   let byteoff = off lsr 3 in
 272   let bitmask = 1 lsl (7 - (off land 7)) in
 273   let b = Char.code data.[byteoff] land bitmask <> 0 in
 274   b, off+1, len-1
 275
 276 (* Returns 8 bit unsigned aligned bytes from the string.
 277  * If the string ends then this returns 0's.
 278  *)
 279 let _get_byte data byteoff strlen =
 280   if strlen > byteoff then Char.code data.[byteoff] else 0
 281 let _get_byte32 data byteoff strlen =
 282   if strlen > byteoff then Int32.of_int (Char.code data.[byteoff]) else 0l
 283 let _get_byte64 data byteoff strlen =
 284   if strlen > byteoff then Int64.of_int (Char.code data.[byteoff]) else 0L
 285
 286 (* Extract [2..8] bits.  Because the result fits into a single
 287  * byte we don't have to worry about endianness, only signedness.
 288  *)
 289 let extract_char_unsigned data off len flen =
 290   let byteoff = off lsr 3 in
 291
 292   (* Optimize the common (byte-aligned) case. *)
 293   if off land 7 = 0 then (
 294     let byte = Char.code data.[byteoff] in
 295     byte lsr (8 - flen), off+flen, len-flen
 296   ) else (
 297     (* Extract the 16 bits at byteoff and byteoff+1 (note that the
 298      * second byte might not exist in the original string).
 299      *)
 300     let strlen = String.length data in
 301
 302     let word =
 303       (_get_byte data byteoff strlen lsl 8) +
 304         _get_byte data (byteoff+1) strlen in
 305
 306     (* Mask off the top bits. *)
 307     let bitmask = (1 lsl (16 - (off land 7))) - 1 in
 308     let word = word land bitmask in
 309     (* Shift right to get rid of the bottom bits. *)
 310     let shift = 16 - ((off land 7) + flen) in
 311     let word = word lsr shift in
 312
 313     word, off+flen, len-flen
 314   )
 315
 316 (* Extract [9..31] bits.  We have to consider endianness and signedness. *)
 317 let extract_int_be_unsigned data off len flen =
 318   let byteoff = off lsr 3 in
 319
 320   let strlen = String.length data in
 321
 322   let word =
 323     (* Optimize the common (byte-aligned) case. *)
 324     if off land 7 = 0 then (
 325       let word =
 326         (_get_byte data byteoff strlen lsl 23) +
 327           (_get_byte data (byteoff+1) strlen lsl 15) +
 328           (_get_byte data (byteoff+2) strlen lsl 7) +
 329           (_get_byte data (byteoff+3) strlen lsr 1) in
 330       word lsr (31 - flen)
 331     ) else if flen <= 24 then (
 332       (* Extract the 31 bits at byteoff .. byteoff+3. *)
 333       let word =
 334         (_get_byte data byteoff strlen lsl 23) +
 335           (_get_byte data (byteoff+1) strlen lsl 15) +
 336           (_get_byte data (byteoff+2) strlen lsl 7) +
 337           (_get_byte data (byteoff+3) strlen lsr 1) in
 338       (* Mask off the top bits. *)
 339       let bitmask = (1 lsl (31 - (off land 7))) - 1 in
 340       let word = word land bitmask in
 341       (* Shift right to get rid of the bottom bits. *)
 342       let shift = 31 - ((off land 7) + flen) in
 343       word lsr shift
 344     ) else (
 345       (* Extract the next 31 bits, slow method. *)
 346       let word =
 347         let c0, off, len = extract_char_unsigned data off len 8 in
 348         let c1, off, len = extract_char_unsigned data off len 8 in
 349         let c2, off, len = extract_char_unsigned data off len 8 in
 350         let c3, off, len = extract_char_unsigned data off len 7 in
 351         (c0 lsl 23) + (c1 lsl 15) + (c2 lsl 7) + c3 in
 352       word lsr (31 - flen)
 353     ) in
 354   word, off+flen, len-flen
 355
 356 let extract_int_le_unsigned data off len flen =
 357   let v, off, len = extract_int_be_unsigned data off len flen in
 358   let v = I.byteswap v flen in
 359   v, off, len
 360
 361 let _make_int32_be c0 c1 c2 c3 =
 362   Int32.logor
 363     (Int32.logor
 364        (Int32.logor
 365           (Int32.shift_left c0 24)
 366           (Int32.shift_left c1 16))
 367        (Int32.shift_left c2 8))
 368     c3
 369
 370 let _make_int32_le c0 c1 c2 c3 =
 371   Int32.logor
 372     (Int32.logor
 373        (Int32.logor
 374           (Int32.shift_left c3 24)
 375           (Int32.shift_left c2 16))
 376        (Int32.shift_left c1 8))
 377     c0
 378
 379 (* Extract exactly 32 bits.  We have to consider endianness and signedness. *)
 380 let extract_int32_be_unsigned data off len flen =
 381   let byteoff = off lsr 3 in
 382
 383   let strlen = String.length data in
 384
 385   let word =
 386     (* Optimize the common (byte-aligned) case. *)
 387     if off land 7 = 0 then (
 388       let word =
 389         let c0 = _get_byte32 data byteoff strlen in
 390         let c1 = _get_byte32 data (byteoff+1) strlen in
 391         let c2 = _get_byte32 data (byteoff+2) strlen in
 392         let c3 = _get_byte32 data (byteoff+3) strlen in
 393         _make_int32_be c0 c1 c2 c3 in
 394       Int32.shift_right_logical word (32 - flen)
 395     ) else (
 396       (* Extract the next 32 bits, slow method. *)
 397       let word =
 398         let c0, off, len = extract_char_unsigned data off len 8 in
 399         let c1, off, len = extract_char_unsigned data off len 8 in
 400         let c2, off, len = extract_char_unsigned data off len 8 in
 401         let c3, _, _ = extract_char_unsigned data off len 8 in
 402         let c0 = Int32.of_int c0 in
 403         let c1 = Int32.of_int c1 in
 404         let c2 = Int32.of_int c2 in
 405         let c3 = Int32.of_int c3 in
 406         _make_int32_be c0 c1 c2 c3 in
 407       Int32.shift_right_logical word (32 - flen)
 408     ) in
 409   word, off+flen, len-flen
 410
 411 let extract_int32_le_unsigned data off len flen =
 412   let v, off, len = extract_int32_be_unsigned data off len flen in
 413   let v = I32.byteswap v flen in
 414   v, off, len
 415
 416 let _make_int64_be c0 c1 c2 c3 c4 c5 c6 c7 =
 417   Int64.logor
 418     (Int64.logor
 419        (Int64.logor
 420           (Int64.logor
 421              (Int64.logor
 422                 (Int64.logor
 423                    (Int64.logor
 424                       (Int64.shift_left c0 56)
 425                       (Int64.shift_left c1 48))
 426                    (Int64.shift_left c2 40))
 427                 (Int64.shift_left c3 32))
 428              (Int64.shift_left c4 24))
 429           (Int64.shift_left c5 16))
 430        (Int64.shift_left c6 8))
 431     c7
 432
 433 (* Extract [1..64] bits.  We have to consider endianness and signedness. *)
 434 let extract_int64_be_unsigned data off len flen =
 435   let byteoff = off lsr 3 in
 436
 437   let strlen = String.length data in
 438
 439   let word =
 440     (* Optimize the common (byte-aligned) case. *)
 441     if off land 7 = 0 then (
 442       let word =
 443         let c0 = _get_byte64 data byteoff strlen in
 444         let c1 = _get_byte64 data (byteoff+1) strlen in
 445         let c2 = _get_byte64 data (byteoff+2) strlen in
 446         let c3 = _get_byte64 data (byteoff+3) strlen in
 447         let c4 = _get_byte64 data (byteoff+4) strlen in
 448         let c5 = _get_byte64 data (byteoff+5) strlen in
 449         let c6 = _get_byte64 data (byteoff+6) strlen in
 450         let c7 = _get_byte64 data (byteoff+7) strlen in
 451         _make_int64_be c0 c1 c2 c3 c4 c5 c6 c7 in
 452       Int64.shift_right_logical word (64 - flen)
 453     ) else (
 454       (* Extract the next 64 bits, slow method. *)
 455       let word =
 456         let c0, off, len = extract_char_unsigned data off len 8 in
 457         let c1, off, len = extract_char_unsigned data off len 8 in
 458         let c2, off, len = extract_char_unsigned data off len 8 in
 459         let c3, off, len = extract_char_unsigned data off len 8 in
 460         let c4, off, len = extract_char_unsigned data off len 8 in
 461         let c5, off, len = extract_char_unsigned data off len 8 in
 462         let c6, off, len = extract_char_unsigned data off len 8 in
 463         let c7, _, _ = extract_char_unsigned data off len 8 in
 464         let c0 = Int64.of_int c0 in
 465         let c1 = Int64.of_int c1 in
 466         let c2 = Int64.of_int c2 in
 467         let c3 = Int64.of_int c3 in
 468         let c4 = Int64.of_int c4 in
 469         let c5 = Int64.of_int c5 in
 470         let c6 = Int64.of_int c6 in
 471         let c7 = Int64.of_int c7 in
 472         _make_int64_be c0 c1 c2 c3 c4 c5 c6 c7 in
 473       Int64.shift_right_logical word (64 - flen)
 474     ) in
 475   word, off+flen, len-flen
 476
 477 (*----------------------------------------------------------------------*)
 478 (* Constructor functions. *)
 479
 480 module Buffer = struct
 481   type t = {
 482     buf : Buffer.t;
 483     mutable len : int;                  (* Length in bits. *)
 484     (* Last byte in the buffer (if len is not aligned).  We store
 485      * it outside the buffer because buffers aren't mutable.
 486      *)
 487     mutable last : int;
 488   }
 489
 490   let create () =
 491     (* XXX We have almost enough information in the generator to
 492      * choose a good initial size.
 493      *)
 494     { buf = Buffer.create 128; len = 0; last = 0 }
 495
 496   let contents { buf = buf; len = len; last = last } =
 497     let data =
 498       if len land 7 = 0 then
 499         Buffer.contents buf
 500       else
 501         Buffer.contents buf ^ (String.make 1 (Char.chr last)) in
 502     data, 0, len
 503
 504   (* Add exactly 8 bits. *)
 505   let add_byte ({ buf = buf; len = len; last = last } as t) byte =
 506     if byte < 0 || byte > 255 then invalid_arg "Bitmatch.Buffer.add_byte";
 507     let shift = len land 7 in
 508     if shift = 0 then
 509       (* Target buffer is byte-aligned. *)
 510       Buffer.add_char buf (Char.chr byte)
 511     else (
 512       (* Target buffer is unaligned.  'last' is meaningful. *)
 513       let first = byte lsr shift in
 514       let second = (byte lsl (8 - shift)) land 0xff in
 515       Buffer.add_char buf (Char.chr (last lor first));
 516       t.last <- second
 517     );
 518     t.len <- t.len + 8
 519
 520   (* Add exactly 1 bit. *)
 521   let add_bit ({ buf = buf; len = len; last = last } as t) bit =
 522     let shift = 7 - (len land 7) in
 523     if shift > 0 then
 524       (* Somewhere in the middle of 'last'. *)
 525       t.last <- last lor ((if bit then 1 else 0) lsl shift)
 526     else (
 527       (* Just a single spare bit in 'last'. *)
 528       let last = last lor if bit then 1 else 0 in
 529       Buffer.add_char buf (Char.chr last);
 530       t.last <- 0
 531     );
 532     t.len <- len + 1
 533
 534   (* Add a small number of bits (definitely < 8).  This uses a loop
 535    * to call add_bit so it's slow.
 536    *)
 537   let _add_bits t c slen =
 538     if slen < 1 || slen >= 8 then invalid_arg "Bitmatch.Buffer._add_bits";
 539     for i = slen-1 downto 0 do
 540       let bit = c land (1 lsl i) <> 0 in
 541       add_bit t bit
 542     done
 543
 544   let add_bits ({ buf = buf; len = len } as t) str slen =
 545     if slen > 0 then (
 546       if len land 7 = 0 then (
 547         if slen land 7 = 0 then
 548           (* Common case - everything is byte-aligned. *)
 549           Buffer.add_substring buf str 0 (slen lsr 3)
 550         else (
 551           (* Target buffer is aligned.  Copy whole bytes then leave the
 552            * remaining bits in last.
 553            *)
 554           let slenbytes = slen lsr 3 in
 555           if slenbytes > 0 then Buffer.add_substring buf str 0 slenbytes;
 556           t.last <- Char.code str.[slenbytes] lsl (8 - (slen land 7))
 557         );
 558         t.len <- len + slen
 559       ) else (
 560         (* Target buffer is unaligned.  Copy whole bytes using
 561          * add_byte which knows how to deal with an unaligned
 562          * target buffer, then call _add_bits for the remaining < 8 bits.
 563          *
 564          * XXX This is going to be dog-slow.
 565          *)
 566         let slenbytes = slen lsr 3 in
 567         for i = 0 to slenbytes-1 do
 568           let byte = Char.code str.[i] in
 569           add_byte t byte
 570         done;
 571         _add_bits t (Char.code str.[slenbytes]) (slen - (slenbytes lsl 3))
 572       );
 573     )
 574 end
 575
 576 (* Construct a single bit. *)
 577 let construct_bit buf b _ =
 578   Buffer.add_bit buf b
 579
 580 (* Construct a field, flen = [2..8]. *)
 581 let construct_char_unsigned buf v flen exn =
 582   let max_val = 1 lsl flen in
 583   if v < 0 || v >= max_val then raise exn;
 584   if flen = 8 then
 585     Buffer.add_byte buf v
 586   else
 587     Buffer._add_bits buf v flen
 588
 589 (* Construct a field of up to 31 bits. *)
 590 let construct_int_be_unsigned buf v flen exn =
 591   (* Check value is within range. *)
 592   if not (I.range_unsigned v flen) then raise exn;
 593   (* Add the bytes. *)
 594   I.map_bytes_be (Buffer._add_bits buf) (Buffer.add_byte buf) v flen
 595
 596 (* Construct a field of up to 64 bits. *)
 597 let construct_int64_be_unsigned buf v flen exn =
 598   (* Check value is within range. *)
 599   if not (I64.range_unsigned v flen) then raise exn;
 600   (* Add the bytes. *)
 601   I64.map_bytes_be (Buffer._add_bits buf) (Buffer.add_byte buf) v flen
 602
 603 (*----------------------------------------------------------------------*)
 604 (* Extract a string from a bitstring. *)
 605
 606 let string_of_bitstring (data, off, len) =
 607   if off land 7 = 0 && len land 7 = 0 then
 608     (* Easy case: everything is byte-aligned. *)
 609     String.sub data (off lsr 3) (len lsr 3)
 610   else (
 611     (* Bit-twiddling case. *)
 612     let strlen = (len + 7) lsr 3 in
 613     let str = String.make strlen '\000' in
 614     let rec loop data off len i =
 615       if len >= 8 then (
 616         let c, off, len = extract_char_unsigned data off len 8 in
 617         str.[i] <- Char.chr c;
 618         loop data off len (i+1)
 619       ) else if len > 0 then (
 620         let c, off, len = extract_char_unsigned data off len len in
 621         str.[i] <- Char.chr c
 622       )
 623     in
 624     loop data off len 0;
 625     str
 626   )
 627
 628 (*----------------------------------------------------------------------*)
 629 (* Display functions. *)
 630
 631 let isprint c =
 632   let c = Char.code c in
 633   c >= 32 && c < 127
 634
 635 let hexdump_bitstring chan (data, off, len) =
 636   let count = ref 0 in
 637   let off = ref off in
 638   let len = ref len in
 639   let linelen = ref 0 in
 640   let linechars = String.make 16 ' ' in
 641
 642   fprintf chan "00000000  ";
 643
 644   while !len > 0 do
 645     let bits = min !len 8 in
 646     let byte, off', len' = extract_char_unsigned data !off !len bits in
 647     off := off'; len := len';
 648
 649     let byte = byte lsl (8-bits) in
 650     fprintf chan "%02x " byte;
 651
 652     incr count;
 653     linechars.[!linelen] <-
 654       (let c = Char.chr byte in
 655        if isprint c then c else '.');
 656     incr linelen;
 657     if !linelen = 8 then fprintf chan " ";
 658     if !linelen = 16 then (
 659       fprintf chan " |%s|\n%08x  " linechars !count;
 660       linelen := 0;
 661       for i = 0 to 15 do linechars.[i] <- ' ' done
 662     )
 663   done;
 664
 665   if !linelen > 0 then (
 666     let skip = (16 - !linelen) * 3 + if !linelen < 8 then 1 else 0 in
 667     for i = 0 to skip-1 do fprintf chan " " done;
 668     fprintf chan " |%s|\n%!" linechars
 669   ) else
 670     fprintf chan "\n%!"