compress.py 5.7 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174
  1. import time
  2. import sys
  3. import array
  4. def prefix(s1, s2):
  5. """ Return the length of the common prefix of s1 and s2 """
  6. sz = len(s2)
  7. for i in range(sz):
  8. if s1[i % len(s1)] != s2[i]:
  9. return i
  10. return sz
  11. def runlength(blk, p0, p1):
  12. """ p0 is the source position, p1 is the dest position
  13. Return the length of run of common chars
  14. """
  15. for i in range(1, len(blk) - p1):
  16. if blk[p0:p0+i] != blk[p1:p1+i]:
  17. return i - 1
  18. return len(blk) - p1 - 1
  19. def runlength2(blk, p0, p1, bsf):
  20. """ p0 is the source position, p1 is the dest position
  21. Return the length of run of common chars
  22. """
  23. if blk[p0:p0+bsf+1] != blk[p1:p1+bsf+1]:
  24. return 0
  25. for i in range(bsf + 1, len(blk) - p1):
  26. if blk[p0:p0+i] != blk[p1:p1+i]:
  27. return i - 1
  28. return len(blk) - p1 - 1
  29. class Bitstream(object):
  30. def __init__(self):
  31. self.b = []
  32. def append(self, sz, v):
  33. assert 0 <= v
  34. assert v < (1 << sz)
  35. for i in range(sz):
  36. self.b.append(1 & (v >> (sz - 1 - i)))
  37. def toarray(self):
  38. bb = [0] * ((len(self.b) + 7) / 8)
  39. for i,b in enumerate(self.b):
  40. if b:
  41. bb[i / 8] |= (1 << (i & 7));
  42. return array.array('B', bb)
  43. class Codec(object):
  44. def __init__(self, b_off, b_len):
  45. self.b_off = b_off
  46. self.b_len = b_len
  47. self.history = 2 ** b_off
  48. refsize = (1 + self.b_off + self.b_len) # bits needed for a backreference
  49. if refsize < 9:
  50. self.M = 1
  51. elif refsize < 18:
  52. self.M = 2
  53. else:
  54. self.M = 3
  55. # print "M", self.M
  56. # e.g. M 2, b_len 4, so: 0->2, 15->17
  57. self.maxlen = self.M + (2**self.b_len) - 1
  58. def compress(self, blk):
  59. lempel = {}
  60. sched = []
  61. pos = 0
  62. while pos < len(blk):
  63. k = blk[pos:pos+self.M]
  64. older = (pos - self.history - 1)
  65. candidates = set([p for p in lempel.get(k, []) if (older < p)])
  66. lempel[k] = candidates # prune old
  67. # print pos, repr(k), len(lempel), "lempels", "candidates", len(candidates)
  68. def addlempel(c):
  69. if c in lempel:
  70. lempel[c].add(pos)
  71. else:
  72. lempel[c] = set([pos])
  73. if 0:
  74. # (bestlen, bestpos) = max([(0, 0)] + [(prefix(blk[p:pos], blk[pos:]), p) for p in candidates])
  75. (bestlen, bestpos) = max([(0, 0)] + [(runlength(blk, p, pos), p) for p in candidates])
  76. bestlen = min(bestlen, self.maxlen)
  77. else:
  78. (bestlen, bestpos) = (0, None)
  79. for p in candidates:
  80. cl = runlength2(blk, p, pos, bestlen)
  81. if cl > bestlen:
  82. bestlen,bestpos = cl,p
  83. if self.maxlen <= bestlen:
  84. bestlen = min(bestlen, self.maxlen)
  85. break
  86. if bestlen >= self.M:
  87. sched.append((bestpos - pos, bestlen))
  88. for i in range(bestlen):
  89. addlempel(blk[pos:pos+self.M])
  90. pos += 1
  91. else:
  92. addlempel(k)
  93. sched.append(blk[pos])
  94. pos += 1
  95. return sched
  96. def toarray(self, blk):
  97. sched = self.compress(blk)
  98. return self.sched2bs(sched)
  99. def sched2bs(self, sched):
  100. bs = Bitstream()
  101. bs.append(4, self.b_off)
  102. bs.append(4, self.b_len)
  103. bs.append(2, self.M)
  104. bs.append(16, len(sched))
  105. for c in sched:
  106. if len(c) != 1:
  107. (offset, l) = c
  108. bs.append(1, 1)
  109. bs.append(self.b_off, -offset - 1)
  110. bs.append(self.b_len, l - self.M)
  111. else:
  112. bs.append(1, 0)
  113. bs.append(8, ord(c))
  114. return bs.toarray()
  115. def to_cfile(self, hh, blk, name):
  116. print >>hh, "static PROGMEM prog_uchar %s[] = {" % name
  117. bb = self.toarray(blk)
  118. for i in range(0, len(bb), 16):
  119. if (i & 0xff) == 0:
  120. print >>hh
  121. for c in bb[i:i+16]:
  122. print >>hh, "0x%02x, " % c,
  123. print >>hh
  124. print >>hh, "};"
  125. def decompress(self, sched):
  126. s = ""
  127. for c in sched:
  128. if len(c) == 1:
  129. s += c
  130. else:
  131. (offset, l) = c
  132. for i in range(l):
  133. s += s[offset]
  134. return s
  135. def main():
  136. from optparse import OptionParser
  137. parser = OptionParser("%prog [ --lookback O ] [ --length L ] --name NAME inputfile outputfile")
  138. parser.add_option("--lookback", type=int, default=8, dest="O", help="lookback field size in bits")
  139. parser.add_option("--length", type=int, default=3, dest="L", help="length field size in bits")
  140. parser.add_option("--name", type=str, default="data", dest="NAME", help="name for generated C array")
  141. parser.add_option("--binary", action="store_true", default=False, dest="binary", help="write a binary file (default is to write a C++ header file)")
  142. options, args = parser.parse_args()
  143. if len(args) != 2:
  144. parser.error("must specify input and output files");
  145. print options.O
  146. print options.L
  147. print options.NAME
  148. print args
  149. (inputfile, outputfile) = args
  150. cc = Codec(b_off = options.O, b_len = options.L)
  151. uncompressed = open(inputfile, "rb").read()
  152. if options.binary:
  153. compressed = cc.toarray(uncompressed)
  154. open(outputfile, "wb").write(compressed.tostring())
  155. else:
  156. outfile = open(outputfile, "w")
  157. cc.to_cfile(outfile, uncompressed, options.NAME)
  158. if __name__ == "__main__":
  159. main()