Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdint.h>
- #include <stddef.h>
- size_t lz77_decode(const uint8_t *src, uint8_t *dst) {
- // size of ring buffer
- static const uint32_t N = 4096;
- // upper limit for match_length
- static const uint32_t F = 18;
- // wrap mask for ring buffer
- static const uint32_t WRAP = N - 1;
- // encode string into position and length if match length > than this
- static const uint32_t THRESHOLD = 2;
- // ring buffer of size N with extra F-1 bytes for string comparison
- uint8_t text_buf[N + F - 1];
- uint32_t i, j;
- // dst base used later to recover bytes written
- const uint8_t *base = dst;
- // clear ring buffer
- for (i = 0; i < N - F; i++) {
- text_buf[i] = ' ';
- }
- // set initial ring position
- uint32_t r = N - F;
- // clear flags
- uint16_t flags = 0;
- // loop until all is decoded
- for (;;) {
- // shift flags down 1 bit
- flags >>= 1;
- // if high byte of flags is 0
- if ((flags & 0xff00) == 0) {
- // read byte
- const uint8_t c = *src++;
- if (!c) break;
- // use high bytes to loop 8 times
- flags = c | 0xff00;
- }
- // if LSB in flags is 1
- if (flags & 1) {
- // read byte
- const uint8_t c = *src++;
- if (!c) break;
- // write byte directly to output
- *(dst++) = c;
- // insert into ring buffer
- text_buf[r++] = c;
- r &= WRAP;
- // if LSB in flags is 0
- } else {
- // read two src byte
- i = *src++;
- j = *src++;
- // high nibble has ring offset high nibble
- i |= (j & 0xf0) << 4;
- // low nibble has entry match count
- j = (j & 0x0f) + THRESHOLD;
- // loop for byte count
- for (int k = 0; k <= j; k++) {
- // read byte from ring buffer
- const uint8_t c = text_buf[(i + k) & WRAP];
- // put byte into output file
- *(dst++) = c;
- // insert into ring buffer
- text_buf[r++] = c;
- r &= WRAP;
- } // for
- }
- } // for
- // number of bytes written
- return dst - base;
- }
Add Comment
Please, Sign In to add comment