123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174 |
- import time
- import sys
- import array
- def prefix(s1, s2):
- """ Return the length of the common prefix of s1 and s2 """
- sz = len(s2)
- for i in range(sz):
- if s1[i % len(s1)] != s2[i]:
- return i
- return sz
- def runlength(blk, p0, p1):
- """ p0 is the source position, p1 is the dest position
- Return the length of run of common chars
- """
- for i in range(1, len(blk) - p1):
- if blk[p0:p0+i] != blk[p1:p1+i]:
- return i - 1
- return len(blk) - p1 - 1
- def runlength2(blk, p0, p1, bsf):
- """ p0 is the source position, p1 is the dest position
- Return the length of run of common chars
- """
- if blk[p0:p0+bsf+1] != blk[p1:p1+bsf+1]:
- return 0
- for i in range(bsf + 1, len(blk) - p1):
- if blk[p0:p0+i] != blk[p1:p1+i]:
- return i - 1
- return len(blk) - p1 - 1
- class Bitstream(object):
- def __init__(self):
- self.b = []
- def append(self, sz, v):
- assert 0 <= v
- assert v < (1 << sz)
- for i in range(sz):
- self.b.append(1 & (v >> (sz - 1 - i)))
- def toarray(self):
- bb = [0] * ((len(self.b) + 7) / 8)
- for i,b in enumerate(self.b):
- if b:
- bb[i / 8] |= (1 << (i & 7));
- return array.array('B', bb)
- class Codec(object):
- def __init__(self, b_off, b_len):
- self.b_off = b_off
- self.b_len = b_len
- self.history = 2 ** b_off
- refsize = (1 + self.b_off + self.b_len) # bits needed for a backreference
- if refsize < 9:
- self.M = 1
- elif refsize < 18:
- self.M = 2
- else:
- self.M = 3
- # print "M", self.M
- # e.g. M 2, b_len 4, so: 0->2, 15->17
- self.maxlen = self.M + (2**self.b_len) - 1
- def compress(self, blk):
- lempel = {}
- sched = []
- pos = 0
- while pos < len(blk):
- k = blk[pos:pos+self.M]
- older = (pos - self.history - 1)
- candidates = set([p for p in lempel.get(k, []) if (older < p)])
- lempel[k] = candidates # prune old
- # print pos, repr(k), len(lempel), "lempels", "candidates", len(candidates)
- def addlempel(c):
- if c in lempel:
- lempel[c].add(pos)
- else:
- lempel[c] = set([pos])
- if 0:
- # (bestlen, bestpos) = max([(0, 0)] + [(prefix(blk[p:pos], blk[pos:]), p) for p in candidates])
- (bestlen, bestpos) = max([(0, 0)] + [(runlength(blk, p, pos), p) for p in candidates])
- bestlen = min(bestlen, self.maxlen)
- else:
- (bestlen, bestpos) = (0, None)
- for p in candidates:
- cl = runlength2(blk, p, pos, bestlen)
- if cl > bestlen:
- bestlen,bestpos = cl,p
- if self.maxlen <= bestlen:
- bestlen = min(bestlen, self.maxlen)
- break
- if bestlen >= self.M:
- sched.append((bestpos - pos, bestlen))
- for i in range(bestlen):
- addlempel(blk[pos:pos+self.M])
- pos += 1
- else:
- addlempel(k)
- sched.append(blk[pos])
- pos += 1
- return sched
- def toarray(self, blk):
- sched = self.compress(blk)
- return self.sched2bs(sched)
- def sched2bs(self, sched):
- bs = Bitstream()
- bs.append(4, self.b_off)
- bs.append(4, self.b_len)
- bs.append(2, self.M)
- bs.append(16, len(sched))
- for c in sched:
- if len(c) != 1:
- (offset, l) = c
- bs.append(1, 1)
- bs.append(self.b_off, -offset - 1)
- bs.append(self.b_len, l - self.M)
- else:
- bs.append(1, 0)
- bs.append(8, ord(c))
- return bs.toarray()
- def to_cfile(self, hh, blk, name):
- print >>hh, "static PROGMEM prog_uchar %s[] = {" % name
- bb = self.toarray(blk)
- for i in range(0, len(bb), 16):
- if (i & 0xff) == 0:
- print >>hh
- for c in bb[i:i+16]:
- print >>hh, "0x%02x, " % c,
- print >>hh
- print >>hh, "};"
- def decompress(self, sched):
- s = ""
- for c in sched:
- if len(c) == 1:
- s += c
- else:
- (offset, l) = c
- for i in range(l):
- s += s[offset]
- return s
- def main():
- from optparse import OptionParser
- parser = OptionParser("%prog [ --lookback O ] [ --length L ] --name NAME inputfile outputfile")
- parser.add_option("--lookback", type=int, default=8, dest="O", help="lookback field size in bits")
- parser.add_option("--length", type=int, default=3, dest="L", help="length field size in bits")
- parser.add_option("--name", type=str, default="data", dest="NAME", help="name for generated C array")
- parser.add_option("--binary", action="store_true", default=False, dest="binary", help="write a binary file (default is to write a C++ header file)")
- options, args = parser.parse_args()
- if len(args) != 2:
- parser.error("must specify input and output files");
- print options.O
- print options.L
- print options.NAME
- print args
- (inputfile, outputfile) = args
- cc = Codec(b_off = options.O, b_len = options.L)
- uncompressed = open(inputfile, "rb").read()
- if options.binary:
- compressed = cc.toarray(uncompressed)
- open(outputfile, "wb").write(compressed.tostring())
- else:
- outfile = open(outputfile, "w")
- cc.to_cfile(outfile, uncompressed, options.NAME)
- if __name__ == "__main__":
- main()
|