BEAR4 compression

WORK IN PROGRESS...

BEAR4 is designed for microcontrollers that have little RAM. It uses the data decompressed so far as the dictionary, compared to typical LZ compression this decreases efficiency since the index range must be larger and the need for storing the count. Most of the loss is recovered by only reading the number of bits required for the current index/count range.

Header

  BE4R - file ID
     w - word size (1-64)
     s - symbol size (1-64) 
     h - symbol shift (0-63)
     i - maximum index size (1-32)
     c - maximum count size (1-16)

Data

0 <symbol>
1 <index> <count>

Pseudocode

do
  indexSize = min(log2(decompressedSize), maximumIndexSize)
  countSize = min(indexSize, maximumCountSize)
  read classBit
  if classBit = 0 then
    read symbol
    output symbol
  else
    read index, count
    for each count
      read symbolFromDecompressed
      output symbol
    next
  endif
loop