Start of documentation.
[ocaml-bitstring.git] / 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.8 2008-04-02 11:06:07 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 (* Display functions. *)
605
606 let isprint c =
607   let c = Char.code c in
608   c >= 32 && c < 127
609
610 let hexdump_bitstring chan (data, off, len) =
611   let count = ref 0 in
612   let off = ref off in
613   let len = ref len in
614   let linelen = ref 0 in
615   let linechars = String.make 16 ' ' in
616
617   fprintf chan "00000000  ";
618
619   while !len > 0 do
620     let bits = min !len 8 in
621     let byte, off', len' = extract_char_unsigned data !off !len bits in
622     off := off'; len := len';
623
624     let byte = byte lsl (8-bits) in
625     fprintf chan "%02x " byte;
626
627     incr count;
628     linechars.[!linelen] <-
629       (let c = Char.chr byte in
630        if isprint c then c else '.');
631     incr linelen;
632     if !linelen = 8 then fprintf chan " ";
633     if !linelen = 16 then (
634       fprintf chan " |%s|\n%08x  " linechars !count;
635       linelen := 0;
636       for i = 0 to 15 do linechars.[i] <- ' ' done
637     )
638   done;
639
640   if !linelen > 0 then (
641     let skip = (16 - !linelen) * 3 + if !linelen < 8 then 1 else 0 in
642     for i = 0 to skip-1 do fprintf chan " " done;
643     fprintf chan " |%s|\n%!" linechars
644   ) else
645     fprintf chan "\n%!"