compiler/bc.lua

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