diskzip/diskzip_bitmap.ml

   1 (* 'diskzip' command for intelligently compressing disk images.
   2    (C) Copyright 2007 Richard W.M. Jones, Red Hat Inc.
   3    http://libvirt.org/
   4
   5    This program is free software; you can redistribute it and/or modify
   6    it under the terms of the GNU General Public License as published by
   7    the Free Software Foundation; either version 2 of the License, or
   8    (at your option) any later version.
   9
  10    This program is distributed in the hope that it will be useful,
  11    but WITHOUT ANY WARRANTY; without even the implied warranty of
  12    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13    GNU General Public License for more details.
  14
  15    You should have received a copy of the GNU General Public License
  16    along with this program; if not, write to the Free Software
  17    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  18  *)
  19
  20 open Int63.Operators
  21
  22 type t = int63 * string array
  23
  24 (* NB: Sys.max_string_length is by no means a 'round' number. *)
  25 let maxlen = Int63.of_int Sys.max_string_length
  26
  27 let create size =
  28   (* Get the size in bytes & round up. *)
  29   let sizebytes = (size +^ ~^7) >^> 3 in
  30
  31   let n = Int63.to_int (sizebytes /^ maxlen) in
  32   let overflow = Int63.to_int (sizebytes %^ maxlen) in
  33   let zerochar = Char.chr 0 in
  34   let array =
  35     if overflow <> 0 then
  36       Array.init (n+1)
  37         (function
  38          | i when i = n -> String.make overflow zerochar
  39          | _ -> String.make Sys.max_string_length zerochar)
  40     else
  41       Array.init n (fun _ -> String.make Sys.max_string_length zerochar) in
  42   size, array
  43
  44 let mask7 = ~^7
  45
  46 let set (size, t) offset =
  47   if offset < Int63.zero || offset >= size then invalid_arg "bitmap";
  48   let offset_bytes, offset_bits =
  49     offset >^> 3,
  50     Int63.to_int (offset &^ mask7) in
  51   let offset_strs, offset_in_str =
  52     Int63.to_int (offset_bytes /^ maxlen),
  53     Int63.to_int (offset_bytes %^ maxlen) in
  54   let c = Char.code t.(offset_strs).[offset_in_str] in
  55   t.(offset_strs).[offset_in_str] <- Char.chr (c lor (1 lsl offset_bits))
  56
  57 let clear (size, t) offset =
  58   if offset < Int63.zero || offset >= size then invalid_arg "bitmap";
  59   let offset_bytes, offset_bits =
  60     offset >^> 3,
  61     Int63.to_int (offset &^ mask7) in
  62   let offset_strs, offset_in_str =
  63     Int63.to_int (offset_bytes /^ maxlen),
  64     Int63.to_int (offset_bytes %^ maxlen) in
  65   let c = Char.code t.(offset_strs).[offset_in_str] in
  66   t.(offset_strs).[offset_in_str] <-
  67     Char.chr (c land (lnot (1 lsl offset_bits)))
  68
  69 let get (size, t) offset =
  70   if offset < Int63.zero || offset >= size then invalid_arg "bitmap";
  71   let offset_bytes, offset_bits =
  72     offset >^> 3,
  73     Int63.to_int (offset &^ mask7) in
  74   let offset_strs, offset_in_str =
  75     Int63.to_int (offset_bytes /^ maxlen),
  76     Int63.to_int (offset_bytes %^ maxlen) in
  77   let c = Char.code t.(offset_strs).[offset_in_str] in
  78   c land (1 lsl offset_bits) <> 0
  79
  80 let set_bool t offset v =
  81   (if v then set else clear) t offset
  82
  83 let set_int t offset v =
  84   (if v <> 0 then set else clear) t offset
  85
  86 let iter_set f (size, t) =
  87   let n = ref Int63.zero in
  88   Array.iter (
  89     fun str ->
  90       let m = ref 0x80 in
  91       for i = 0 to String.length str - 1 do
  92         let c = Char.code str.[i] in
  93         for j = 0 to 7 do
  94           let n' = !n in
  95           if n' < size then (
  96             let b = c land !m <> 0 in
  97             let b = f n' b in
  98             str.[i] <- Char.chr (if b then c lor !m else c land lnot !m)
  99           );
 100           n := Int63.succ n';
 101           m := !m lsr 1
 102         done
 103       done
 104   ) t
 105
 106 let iter f t =
 107   let f i b = f i b; b in
 108   iter_set f t