he3.rb

   1 # This file came from Asami (http://asami.rubyforge.org). There is no LICENSE\r
   2 # distributed with the Asami project. I have no idea what license the Asami project\r
   3 # is intended to be distributed under, but in the absence of other information I\r
   4 # will assume the Ruby license.\r
   5 \r
   6 def huff_insert(arr,node)\r
   7         return arr.unshift(node) if arr.length==0\r
   8         0.upto(arr.length-1){|i|\r
   9                 if arr[i].occur>node.occur\r
  10                         if i>0\r
  11                                 return arr[0..i-1]+[node]+arr[i..arr.length]\r
  12                         else\r
  13                                 return arr.unshift(node)\r
  14                         end\r
  15                 elsif arr[i].occur == node.occur && (node.left==nil)\r
  16                         if i>0\r
  17                                 return arr[0..i-1]+[node]+arr[i..arr.length]\r
  18                         else\r
  19                                 return arr.unshift(node)\r
  20                         end\r
  21                 end\r
  22         }\r
  23         return arr.push(node)\r
  24 end\r
  25 def add_bit(str,pos,value)\r
  26         str << 0 if pos&7==0\r
  27         if value!=0\r
  28                 str[pos/8]|=(1<<(pos&7))\r
  29         end\r
  30 end\r
  31 def add_bits(str,pos,pattern,len)\r
  32         0.upto(len-1){|i|\r
  33                 add_bit(str,pos,pattern>>(len-1-i)&1)\r
  34                 pos+=1\r
  35         }\r
  36 end\r
  37 def get_bit(str,pos)\r
  38         ((str[pos/8]) >> (pos&7))&1\r
  39 end\r
  40 def get_bits(str,start,num)\r
  41         res=0\r
  42         0.upto(num-1){|i|res=res<<1|get_bit(str,start+i);}\r
  43         res\r
  44 end\r
  45 \r
  46 class HuffNode\r
  47   attr_accessor :left,:right,:occur,:value\r
  48   def initialize(occur,value)\r
  49     @occur=occur\r
  50     @value=value\r
  51     @left=nil\r
  52     @right=nil\r
  53   end\r
  54 end\r
  55 class HufEncode\r
  56   attr_reader :len,:bits\r
  57   def initialize(len,bits)\r
  58     @len=len\r
  59     @bits=bits\r
  60   end\r
  61 end\r
  62 \r
  63 def use_hufnode(tbl_enc,node,length,bits)\r
  64   if node.left!=nil\r
  65     use_hufnode(tbl_enc,node.left,length+1,(bits<<1)|0)\r
  66     use_hufnode(tbl_enc,node.right,length+1,(bits<<1)|1)\r
  67   else\r
  68     idx=node.value&255\r
  69     tbl_enc[idx]=HufEncode.new length,bits\r
  70   end\r
  71 end\r
  72 \r
  73 def he3_encode(str)\r
  74   tbl_enc=Array.new\r
  75   data=""\r
  76   list=Array.new\r
  77   nb_val=0\r
  78   occur=Array.new 256,0\r
  79   if str==nil||str.length==0\r
  80     puts "zero length or nil string"\r
  81   end\r
  82   parity=0\r
  83   0.upto(str.length-1){|i|\r
  84     occur[(str[i]&255)]+=1\r
  85     parity^=str[i]\r
  86   }\r
  87   0.upto(255){|i|\r
  88     if occur[i]!=0\r
  89       mw=HuffNode.new(occur[i],i)\r
  90       list=huff_insert(list,mw)\r
  91       nb_val+=1\r
  92     end\r
  93   }\r
  94   while(list.length>1)\r
  95     node=HuffNode.new(0,0)\r
  96     node.left=list.shift\r
  97     node.right=list.shift\r
  98     node.occur=(node.left.occur||0)+(node.right.occur||0)\r
  99     list=huff_insert(list,node)\r
 100   end\r
 101   root_huff=list.shift\r
 102   use_hufnode tbl_enc,root_huff,0,0\r
 103   header="HE3\r0000000"\r
 104   header[4]=(parity&255)\r
 105   header[5]=str.length&255\r
 106   header[6]=(str.length>>8)&255\r
 107   header[7]=(str.length>>16)&255\r
 108   header[8]=(str.length>>24)&255\r
 109   header[9]=nb_val&255\r
 110   header[10]=(nb_val>>8)&255\r
 111   data = header\r
 112   0.upto(255){|i|\r
 113     if occur[i]!=0\r
 114       data << i\r
 115       data << tbl_enc[i].len\r
 116     end\r
 117   }\r
 118   bit_pos=data.length*8\r
 119         0.upto(255){|i|\r
 120     if occur[i]!=0\r
 121       add_bits(data,bit_pos,tbl_enc[i].bits,tbl_enc[i].len)\r
 122       bit_pos+=tbl_enc[i].len;\r
 123     end\r
 124   }\r
 125   bit_pos=(bit_pos+7)&~7\r
 126   0.upto(str.length-1){|i|\r
 127     idx=str[i]&255\r
 128     add_bits(data,bit_pos,tbl_enc[idx].bits,tbl_enc[idx].len)\r
 129     bit_pos+=tbl_enc[idx].len\r
 130   }\r
 131   return data\r
 132 end\r
 133 \r
 134 def he3_decode(input)\r
 135   unless input[0]==72 && input[1]==69 && input[2]==51 && input[3]==13\r
 136     puts "not a valid he3 i guess"\r
 137     exit\r
 138   end\r
 139   nb_output=0\r
 140   8.downto(6){|i|\r
 141     nb_output|=(input[i]&255)\r
 142     nb_output<<=8\r
 143   }\r
 144   nb_output|=(input[5]&255)\r
 145   nb_couple = input[9]\r
 146   nb_couple += ((input[10]&255)<<8)\r
 147   max_len=0\r
 148   total_len=0\r
 149   0.upto(nb_couple-1){|pos|\r
 150     v = input[12+pos*2]&255\r
 151     max_len = v if v>max_len\r
 152     total_len+=v\r
 153   }\r
 154   offset_pattern = 8 *(11+nb_couple*2)\r
 155   offset_encoded=offset_pattern + ((total_len+7)&~7)\r
 156   decode_array=Array.new max_len*32,0\r
 157   0.upto(nb_couple-1){|pos|\r
 158     v_len = input[12+pos*2]&255\r
 159     value = get_bits(input,offset_pattern,v_len)\r
 160     offset_pattern+=v_len\r
 161     decode_array[(1<<v_len)+value] = input[11+pos*2]    \r
 162   }\r
 163   output=""\r
 164   while output.length!=(nb_output) do\r
 165     cur_val = get_bit(input,offset_encoded)\r
 166     offset_encoded+=1\r
 167     nb_bit_val=1\r
 168     x=decode_array[(1<<nb_bit_val)+cur_val]\r
 169     while(x==0||x==nil) do\r
 170       cur_val=cur_val<<1|get_bit(input,offset_encoded)\r
 171       offset_encoded+=1\r
 172       nb_bit_val+=1\r
 173       x=decode_array[(1<<nb_bit_val)+cur_val]\r
 174     end\r
 175     output << (decode_array[(1<<nb_bit_val)+cur_val])\r
 176   end\r
 177   return output\r
 178 end\r
 179 \r
 180 \r