summaryrefslogtreecommitdiff
path: root/cesar/mac/pbproc/src/sacki_tables.py
diff options
context:
space:
mode:
Diffstat (limited to 'cesar/mac/pbproc/src/sacki_tables.py')
-rw-r--r--cesar/mac/pbproc/src/sacki_tables.py258
1 files changed, 258 insertions, 0 deletions
diff --git a/cesar/mac/pbproc/src/sacki_tables.py b/cesar/mac/pbproc/src/sacki_tables.py
new file mode 100644
index 0000000000..24b124afe5
--- /dev/null
+++ b/cesar/mac/pbproc/src/sacki_tables.py
@@ -0,0 +1,258 @@
+codes = {
+ '11': '11111',
+ '101': '101111',
+ '001': '011',
+ '110': '001111',
+ '010': '001',
+ '100': '101',
+ '1000': '0111',
+ '0000': '0',
+ }
+
+class Binary:
+ """Store a binary number and its number of bits."""
+
+ def __init__ (self, value = '', bits = None):
+ if bits:
+ self.value = value
+ self.bits = bits
+ else:
+ self.value = 0
+ self.bits = 0
+ for b in value:
+ assert b == '0' or b == '1'
+ self.value *= 2
+ if b == '1':
+ self.value += 1
+ self.bits += 1
+
+ def __str__ (self):
+ """Transform to a string"""
+ if self.bits == 0:
+ return ''
+ s = ''
+ b = 1 << (self.bits - 1)
+ while b:
+ if self.value & b:
+ s += '1'
+ else:
+ s += '0'
+ b >>= 1
+ return s
+
+ def __repr__ (self):
+ return "'" + str (self) + "'"
+
+ def __iadd__ (self, other):
+ """Concatenate two binary numbers."""
+ self.value = (other.value << self.bits) | self.value
+ self.bits += other.bits
+ return self
+
+ def __irshift__ (self, other):
+ """Drop a number of least significant bits."""
+ assert (other <= self.bits)
+ self.value >>= other
+ self.bits -= other
+ return self
+
+ def imask (self, other):
+ """Mask a number of bits."""
+ assert (other <= self.bits)
+ self.value &= (1 << other) - 1
+ self.bits = other
+
+ def match (self, other):
+ """Return true if this binary number match the other. I.e. if the
+ other number start with this one."""
+ return (self.bits <= other.bits
+ and (other.value & ((1 << self.bits) - 1)) == self.value)
+
+ def copy (self):
+ i = Binary ()
+ i.value = self.value
+ i.bits = self.bits
+ return i
+
+ def posone (self):
+ """Return the list of positions of ones."""
+ pos = list ()
+ for i in range (self.bits):
+ b = 1 << i
+ if self.value & b:
+ pos.append (i)
+ return pos
+
+class Table:
+ """Conversion table."""
+
+ def __init__ (self, codes):
+ t = [(Binary (a), Binary (b)) for (a, b) in codes.iteritems ()]
+ t.sort (key=(lambda x: x[1].bits))
+ self.table = t
+
+ def __repr__ (self):
+ return 'table: ' + repr (self.table)
+
+ def encode_chunk (self, c, free_pad = False, slow = False):
+ """Encode a chunk using the table and return the precomputed result.
+ - c: chunk to encode.
+ - free_pad: can pad with any bits.
+ - slow: only output one code.
+
+ Will return (eat, code) when not padding and (code, pad) when padding.
+ """
+ cc = c.copy ()
+ out = Binary ()
+ while cc.bits:
+ for (f, t) in self.table:
+ if f.match (cc):
+ out += t
+ cc >>= f.bits
+ break
+ else:
+ break
+ if slow:
+ break
+ if not free_pad:
+ return (c.bits - cc.bits, out)
+ else:
+ # Here, there is no code corresponding exactly.
+ if cc.bits == 0:
+ return (out, 0)
+ for (f, t) in self.table:
+ if cc.match (f):
+ out += t
+ return (out, f.bits - cc.bits)
+ assert 0
+
+encode_table = Table (codes)
+decode_table = Table (dict ([(a, b) for (b, a) in codes.iteritems ()]))
+
+import sys
+
+assert sys.argv[1] in ('enc', 'dec')
+
+print '''/*
+ * Automatically generated file, do not edit!
+ */'''
+
+if sys.argv[1] == 'enc':
+ print '''
+/** The fast table is used for main stream encoding, going as fast as
+ * possible. */
+struct sack_enc_fast_t
+{
+ u32 code:20;
+ u32 codel:5;
+ u32 eat:4;
+};
+'''
+
+ print 'static const struct sack_enc_fast_t sack_enc_8[] = {'
+ for i in range (256):
+ ib = Binary (i, 8)
+ (eat, ob) = encode_table.encode_chunk (ib)
+ pre = ib.copy ()
+ pre >>= eat
+ ib.imask (eat)
+ print ' { 0x%05x, %2d, %d }, /* %s_%s => %20s */' % (ob.value,
+ ob.bits, eat, pre, ib, ob)
+ print '};'
+
+ print '''
+/** The slow table is used until there is only 0, 1, 2 or 3 bits
+ * remaining. */
+struct sack_enc_slow_t
+{
+ u16 code:10;
+ u16 codel:4;
+ u16 eat_m1:2;
+};
+'''
+
+ print 'static const struct sack_enc_slow_t sack_enc_4[] = {'
+ for i in range (16):
+ ib = Binary (i, 4)
+ (eat, ob) = encode_table.encode_chunk (ib)
+ pre = ib.copy ()
+ pre >>= eat
+ ib.imask (eat)
+ print ' { 0x%03x, %2d, %d - 1 }, /* %s_%s => %10s */' % (ob.value,
+ ob.bits, eat, pre, ib, ob)
+ print '};'
+
+ print '''
+/** The finishing tables are used to select the right code to stop the
+ * stream. The input stream can be padded to select the best (shortest)
+ * code. */
+struct sack_enc_finish_t
+{
+ u16 code:8;
+ u16 codel:4;
+};
+'''
+
+ for t in range (3):
+ print 'static const struct sack_enc_finish_t sack_enc_f%d[] = {' % (t
+ + 1)
+ for i in range (1 << (t + 1)):
+ ib = Binary (i, t + 1)
+ (ob, pad) = encode_table.encode_chunk (ib, free_pad = True)
+ print ' { 0x%02x, %d }, /* %3s%s => %8s */' % (ob.value,
+ ob.bits, 'x' * pad, ib, ob)
+ print '};'
+
+if sys.argv[1] == 'dec':
+ print '''
+/** The fast decoding table is used for main stream decoding, going as
+ * fast as possible. */
+struct sack_dec_fast_t
+{
+ u32 eat:4;
+ u32 prod:6;
+#define SACK_DEC_FAST_NOK_UNDEF 31
+ u32 nok0:5;
+ u32 nok1:5;
+ u32 nok2:5;
+};
+'''
+
+ print 'static const struct sack_dec_fast_t sack_dec_fast[] = {'
+ for i in range (256):
+ ib = Binary (i, 8)
+ (eat, ob) = decode_table.encode_chunk (ib)
+ pre = ib.copy ()
+ pre >>= eat
+ ib.imask (eat)
+ pos = (ob.posone () + [ 31, 31, 31 ])[0:3]
+ print ' { %d, %2d, %2d, %2d, %2d }, /* %s_%s => %32s */' % (eat,
+ ob.bits, pos[0], pos[1], pos[2], pre, ib, ob)
+ print '};'
+
+ print '''
+/** But sooner or later, the algorithm must slow down in order not to eat
+ * too much bits. */
+struct sack_dec_slow_t
+{
+ u16 eat:3;
+ u16 prod:3;
+#define SACK_DEC_SLOW_NOK_UNDEF 7
+ u16 nok0:3;
+ u16 nok1:3;
+};
+'''
+
+ print 'static const struct sack_dec_slow_t sack_dec_slow[] = {'
+ for i in range (64):
+ ib = Binary (i, 6)
+ (eat, ob) = decode_table.encode_chunk (ib, slow = True)
+ pre = ib.copy ()
+ pre >>= eat
+ ib.imask (eat)
+ pos = (ob.posone () + [ 7, 7 ])[0:2]
+ print ' { %d, %d, %d, %d }, /* %s_%s => %4s */' % (eat,
+ ob.bits, pos[0], pos[1], pre, ib, ob)
+ print '};'
+
+print ''