compiler/bc.lua

   1 --[[--------------------------------------------------------------------
   2
   3   bc.lua
   4
   5   A quick and dirty module for writing files in Bitcode format.
   6
   7   Copyright (c) 2007 Joshua Haberman.  See LICENSE for details.
   8
   9 --------------------------------------------------------------------]]--
  10
  11 module("bc", package.seeall)
  12
  13 END_BLOCK = 0
  14 ENTER_SUBBLOCK = 1
  15 DEFINE_ABBREV = 2
  16 UNABBREV_RECORD = 3
  17
  18 ENCODING_FIXED = 1
  19 ENCODING_VBR = 2
  20 ENCODING_ARRAY = 3
  21 ENCODING_CHAR6 = 4
  22
  23 BLOCKINFO = 0
  24
  25 SETBID = 1
  26
  27 LiteralOp = {name="LiteralOp"}
  28 function LiteralOp:new(value)
  29   local obj = newobject(self)
  30   obj.value = value
  31   return obj
  32 end
  33
  34 VBROp = {name="VBROp"}
  35 function VBROp:new(bits)
  36   local obj = newobject(self)
  37   obj.bits = bits
  38   obj.name = name
  39   return obj
  40 end
  41
  42 FixedOp = {name="FixedOp"}
  43 function FixedOp:new(bits)
  44   local obj = newobject(self)
  45   obj.bits = bits
  46   obj.name = name
  47   return obj
  48 end
  49
  50 ArrayOp = {name="ArrayOp"}
  51 function ArrayOp:new(elem_type)
  52   local obj = newobject(self)
  53   obj.elem_type = elem_type
  54   obj.name = name
  55   return obj
  56 end
  57
  58 File = {name="File"}
  59 function File:new(filename, app_magic_number)
  60   local obj = newobject(self)
  61   obj.name = name
  62   obj.file = io.open(filename, "w")
  63   obj.current_byte = 0
  64   obj.current_bits = 0
  65   obj.file:write("BC")
  66   obj.file:write(app_magic_number)
  67   obj.current_abbrev_width = 2
  68   obj.offset = 0
  69   obj.stack = {}
  70   return obj
  71 end
  72
  73 -- Witness the joy of trying to do bitwise manipulation in a language that
  74 -- has no bitwise operators.
  75 function File:write_fixed(val, bits)
  76   -- print(string.format("Write fixed: %d, %d", val, bits))
  77   -- print(string.format("Existing bytes(%d): %d", self.current_bits, self.current_byte))
  78   while bits > 0 do
  79     local bits_this_byte = math.min(8-self.current_bits, bits)
  80     local low_bits = val % (2 ^ bits_this_byte)
  81     self.current_byte = self.current_byte + (low_bits * (2 ^ self.current_bits))
  82     self.current_bits = self.current_bits + bits_this_byte
  83     if self.current_bits == 8 then
  84       -- print(string.format("Flushing byte %d", self.current_byte))
  85       self.file:write(string.char(self.current_byte))
  86       self.current_byte = 0
  87       self.current_bits = 0
  88       self.offset = self.offset + 1
  89     end
  90     bits = bits - bits_this_byte
  91     val = math.floor(val / (2 ^ bits_this_byte))
  92   end
  93 end
  94
  95 function File:align_32_bits()
  96   if self.current_bits > 0 then
  97     self:write_fixed(0, 8-self.current_bits)
  98   end
  99
 100   if self.offset % 4 > 0 then
 101     self:write_fixed(0, (4 - (self.offset % 4)) * 8)
 102   end
 103 end
 104
 105 function File:write_vbr(val, bits)
 106   -- print(string.format("Write VBR: %d, %d", val, bits))
 107   local high_bit = 2 ^ (bits-1)
 108   local bits_remaining
 109
 110   if val == 0 then
 111     bits_remaining = 1
 112   else
 113     bits_remaining = 1 + math.floor(math.log(val) / math.log(2))
 114   end
 115
 116   while true do
 117     if bits_remaining > (bits-1) then
 118       self:write_fixed(high_bit + (val % high_bit), bits)
 119       bits_remaining = bits_remaining - (bits-1)
 120       val = math.floor(val / high_bit)
 121     else
 122       self:write_fixed(val, bits)
 123       break
 124     end
 125   end
 126 end
 127
 128 function File:enter_subblock(block_id)
 129   -- print(string.format("++ Enter subblock: %d", block_id))
 130   local old_abbrev_width = self.current_abbrev_width
 131   self:write_fixed(ENTER_SUBBLOCK, self.current_abbrev_width)
 132   self:write_vbr(block_id, 8)
 133   self:write_vbr(4, 4)  -- no need to make this configurable at the moment
 134   self.current_abbrev_width = 4
 135   self:align_32_bits()
 136
 137   self:write_fixed(0, 32)   -- we'll fill this in later
 138   table.insert(self.stack, {old_abbrev_width, self.file:seek()})
 139 end
 140
 141 function File:end_subblock(block_id)
 142   -- print(string.format("-- End subblock: %d", block_id))
 143   self:write_fixed(END_BLOCK, self.current_abbrev_width)
 144   self:align_32_bits()
 145   local block_offset
 146   self.current_abbrev_width, block_offset = unpack(table.remove(self.stack))
 147   local current_offset = self.file:seek()
 148   self.file:seek("set", block_offset - 4)
 149   self:write_fixed((current_offset - block_offset) / 4, 32)
 150   self.file:seek("set", current_offset)
 151 end
 152
 153 function File:write_unabbreviated_record(id, ...)
 154   -- print(string.format("Write unabbreviated record: %d", id))
 155   local args = {...}
 156   self:write_fixed(UNABBREV_RECORD, self.current_abbrev_width)
 157   self:write_vbr(id, 6)
 158   self:write_vbr(#args, 6)
 159   for arg in each(args) do
 160     self:write_vbr(arg, 6)
 161   end
 162 end
 163
 164 function File:write_abbreviated_val(val, op)
 165   if op.class == VBROp then
 166     self:write_vbr(val, op.bits)
 167   elseif op.class == FixedOp then
 168     self:write_fixed(val, op.bits)
 169   else
 170     error("Unknown op type!")
 171   end
 172 end
 173
 174 function File:write_abbreviated_record(abbreviation, ...)
 175   -- print("Write abbreviated record:" .. serialize({...}))
 176   local args = {...}
 177   if #args ~= #abbreviation.ops then
 178     error("Wrong number of arguments for abbreviated record")
 179   end
 180   self:write_fixed(abbreviation.id, self.current_abbrev_width)
 181   for i, arg in ipairs(args) do
 182     local op = abbreviation.ops[i]
 183     if op.class == ArrayOp then
 184       self:write_vbr(arg:len(), 6)
 185       for int in each({arg:byte(1, arg:len())}) do
 186         self:write_abbreviated_val(int, op.elem_type)
 187       end
 188     else
 189       self:write_abbreviated_val(arg, op)
 190     end
 191   end
 192 end
 193
 194 function File:write_abbrev_op(arg)
 195   if arg.class == LiteralOp then
 196     self:write_fixed(1, 1)
 197     self:write_vbr(arg.value, 8)
 198   elseif arg.class == VBROp then
 199     self:write_fixed(0, 1)
 200     self:write_fixed(ENCODING_VBR, 3)
 201     self:write_vbr(arg.bits, 5)
 202   elseif arg.class == FixedOp then
 203     self:write_fixed(0, 1)
 204     self:write_fixed(ENCODING_FIXED, 3)
 205     self:write_vbr(arg.bits, 5)
 206   else
 207     error("Unknown/unhandled op type")
 208   end
 209 end
 210
 211 function File:define_abbreviation(abbrev_id, ...)
 212   local abbrev = {id=abbrev_id, ops={}}
 213   local args = {...}
 214   self:write_fixed(DEFINE_ABBREV, self.current_abbrev_width)
 215   if args[#args].class == ArrayOp then
 216     self:write_vbr(#args+1, 5)
 217   else
 218     self:write_vbr(#args, 5)
 219   end
 220
 221   for arg in each(args) do
 222     if arg.class ~= LiteralOp then
 223       table.insert(abbrev.ops, arg)
 224     end
 225
 226     if arg.class == ArrayOp then
 227       self:write_fixed(0, 1)
 228       self:write_fixed(ENCODING_ARRAY, 3)
 229       self:write_abbrev_op(arg.elem_type)
 230     else
 231       self:write_abbrev_op(arg)
 232     end
 233   end
 234   return abbrev
 235 end
 236
 237 -- vim:et:sts=2:sw=2