/*
* Copyright (c) 1988-1997 Sam Leffler
* Copyright (c) 1991-1997 Silicon Graphics, Inc.
*
* Permission to use, copy, modify, distribute, and sell this software and
* its documentation for any purpose is hereby granted without fee, provided
* that (i) the above copyright notices and this permission notice appear in
* all copies of the software and related documentation, and (ii) the names of
* Sam Leffler and Silicon Graphics may not be used in any advertising or
* publicity relating to the software without the specific, prior written
* permission of Sam Leffler and Silicon Graphics.
*
* THE SOFTWARE IS PROVIDED "AS-IS" AND WITHOUT WARRANTY OF ANY KIND,
* EXPRESS, IMPLIED OR OTHERWISE, INCLUDING WITHOUT LIMITATION, ANY
* WARRANTY OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
*
* IN NO EVENT SHALL SAM LEFFLER OR SILICON GRAPHICS BE LIABLE FOR
* ANY SPECIAL, INCIDENTAL, INDIRECT OR CONSEQUENTIAL DAMAGES OF ANY KIND,
* OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
* WHETHER OR NOT ADVISED OF THE POSSIBILITY OF DAMAGE, AND ON ANY THEORY OF
* LIABILITY, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE
* OF THIS SOFTWARE.
*/
/*
* Portions Copyright (C) 2016 Cisco and/or its affiliates. All rights reserved.
*
* Modified by: Kevin Lin
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License version 2 as
* published by the Free Software Foundation.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
* MA 02110-1301, USA.
*
* In addition, as a special exception, the copyright holders give
* permission to link the code of portions of this program with the
* OpenSSL library under certain conditions as described in each
* individual source file, and distribute linked combinations
* including the two.
*
* You must obey the GNU General Public License in all respects
* for all of the code used other than OpenSSL. If you modify
* file(s) with this exception, you may extend this exception to your
* version of the file(s), but you are not obligated to do so. If you
* do not wish to do so, delete this exception statement from your
* version. If you delete this exception statement from all source
* files in the program, then also delete it here.
*/
#include <stdio.h>
#include <assert.h>
#include <stdint.h>
#include "lzwdec.h"
#include "../others.h"
#define MAXCODE(n) ((1L<<(n))-1)
/*
* The spec specifies that encoded bit
* strings SHOULD range from 9 to 12 bits.
*/
#define BITS_MIN 9 /* start with 9 bits */
#define BITS_VALID 12 /* 12 bit codes are the max valid */
#define BITS_MAX 14 /* max of 14 bit codes (2 bits extension) */
/* predefined codes */
#define CODE_BASIC 256 /* last basic code + 1 */
#define CODE_CLEAR 256 /* code to clear string table */
#define CODE_EOI 257 /* end-of-information code */
#define CODE_FIRST 258 /* first free code entry */
#define CODE_VALID MAXCODE(BITS_VALID)
#define CODE_MAX MAXCODE(BITS_MAX)
#define CSIZE (MAXCODE(BITS_MAX)+1L)
typedef uint16_t hcode_t; /* codes fit in 16 bits */
/*
* Decoding-specific state.
*/
typedef struct code_ent {
struct code_ent *next;
uint16_t length; /* string len, including this token */
uint8_t value; /* data value */
uint8_t firstchar; /* first token of string */
} code_t;
struct lzw_internal_state {
/* general state */
uint16_t nbits; /* # of bits/code */
unsigned long nextdata; /* next bits of i/o */
long nextbits; /* # of valid bits in lzw_nextdata */
/* decoding-specific state */
long dec_nbitsmask; /* lzw_nbits 1 bits, right adjusted */
long dec_restart; /* restart count */
code_t *dec_codep; /* current recognized code */
code_t *dec_oldcodep; /* previously recognized code */
code_t *dec_free_entp; /* next free entry */
code_t *dec_maxcodep; /* max available entry */
code_t *dec_codetab; /* kept separate for small machines */
};
static void code_print(code_t *code);
static void dict_print(code_t *codetab, uint16_t start, uint16_t maxcode);
#define GetNextCode(code) { \
if (have == 0) \
break; \
nextdata = nextdata << 8 | *(from)++; \
have--; \
nextbits += 8; \
if (nextbits < nbits) { \
if (have == 0) \
break; \
nextdata = nextdata << 8 | *(from)++; \
have--; \
nextbits += 8; \
} \
code = (hcode_t)((nextdata >> (nextbits-nbits)) & nbitsmask); \
nextbits -= nbits; \
}
#define CodeClear(code) { \
free_code = CODE_FIRST; \
free_entp = state->dec_codetab + CODE_FIRST; \
nbits = BITS_MIN; \
nbitsmask = MAXCODE(BITS_MIN); \
maxcodep = state->dec_codetab + nbitsmask-1; \
while (code == CODE_CLEAR) /* clears out consecutive CODE_CLEARs */ \
GetNextCode(code); \
if (code < CODE_BASIC) \
*to++ = code, left--; \
else if (code == CODE_EOI) \
ret = LZW_STREAM_END; \
else if (code >= CODE_FIRST) { \
/* cannot reference unpopulated dictionary entries */ \
strm->msg = "cannot reference unpopulated dictionary entries"; \
ret = LZW_DATA_ERROR; \
} \
oldcodep = state->dec_codetab + code; \
}
int lzwInit(lzw_streamp strm)
{
struct lzw_internal_state *state;
hcode_t code;
state = cli_malloc(sizeof(struct lzw_internal_state));
if (state == NULL) {
strm->msg = "failed to allocate state";
return LZW_MEM_ERROR;
}
/* general state setup */
state->nbits = BITS_MIN;
state->nextdata = 0;
state->nextbits = 0;
/* dictionary setup */
state->dec_codetab = cli_calloc(CSIZE, sizeof(code_t));
if (state->dec_codetab == NULL) {
free(state);
strm->msg = "failed to allocate code table";
return LZW_MEM_ERROR;
}
for (code = 0; code < CODE_BASIC; code++) {
state->dec_codetab[code].next = NULL;
state->dec_codetab[code].length = 1;
state->dec_codetab[code].value = code;
state->dec_codetab[code].firstchar = code;
}
state->dec_restart = 0;
state->dec_nbitsmask = MAXCODE(BITS_MIN);
state->dec_free_entp = state->dec_codetab + CODE_FIRST;
state->dec_oldcodep = &state->dec_codetab[CODE_CLEAR];
state->dec_maxcodep = &state->dec_codetab[state->dec_nbitsmask-1];
strm->state = state;
return LZW_OK;
}
int lzwInflate(lzw_streamp strm)
{
struct lzw_internal_state *state;
uint8_t *from, *to;
unsigned in, out;
unsigned have, left;
long nbits, nextbits, nbitsmask;
unsigned long nextdata;
code_t *codep, *free_entp, *maxcodep, *oldcodep;
uint8_t *wp;
hcode_t code, free_code;
int echg, cext, ret = LZW_OK;
uint32_t flags;
if (strm == NULL || strm->state == NULL || strm->next_out == NULL ||
(strm->next_in == NULL && strm->avail_in != 0))
return LZW_STREAM_ERROR;
/* load state */
to = strm->next_out;
out = left = strm->avail_out;
from = strm->next_in;
in = have = strm->avail_in;
flags = strm->flags;
state = strm->state;
nbits = state->nbits;
nextdata = state->nextdata;
nextbits = state->nextbits;
nbitsmask = state->dec_nbitsmask;
oldcodep = state->dec_oldcodep;
free_entp = state->dec_free_entp;
maxcodep = state->dec_maxcodep;
echg = flags & LZW_FLAG_EARLYCHG;
cext = flags & LZW_FLAG_EXTNCODE;
free_code = free_entp - &state->dec_codetab[0];
if (oldcodep == &state->dec_codetab[CODE_EOI])
return LZW_STREAM_END;
/*
* Restart interrupted output operation.
*/
if (state->dec_restart) {
long residue;
codep = state->dec_codep;
residue = codep->length - state->dec_restart;
if (residue > left) {
/*
* Residue from previous decode is sufficient
* to satisfy decode request. Skip to the
* start of the decoded string, place decoded
* values in the output buffer, and return.
*/
state->dec_restart += left;
do {
codep = codep->next;
} while (--residue > left);
to = wp = to + left;
do {
*--wp = codep->value;
codep = codep->next;
} while (--left);
goto inf_end;
}
/*
* Residue satisfies only part of the decode request.
*/
to += residue, left -= residue;
wp = to;
do {
*--wp = codep->value;
codep = codep->next;
} while (--residue);
state->dec_restart = 0;
}
/* guarantee valid initial state */
if (left > 0 && (oldcodep == &state->dec_codetab[CODE_CLEAR])) {
code = CODE_CLEAR;
CodeClear(code);
if (ret != LZW_OK)
goto inf_end;
}
while (left > 0) {
GetNextCode(code);
if (code == CODE_EOI) {
ret = LZW_STREAM_END;
break;
}
if (code == CODE_CLEAR) {
CodeClear(code);
if (ret != LZW_OK)
break;
continue;
}
codep = state->dec_codetab + code;
/* cap dictionary codes to valid range (12-bits) */
if (free_code < CODE_VALID+1 || cext) {
/* non-earlychange bit expansion */
if (!echg && free_entp > maxcodep) {
if (++nbits > BITS_VALID) {
if (!cext)
nbits = BITS_VALID;
else if (nbits > BITS_MAX)
nbits = BITS_MAX;
}
nbitsmask = MAXCODE(nbits);
maxcodep = state->dec_codetab + nbitsmask-1;
}
/*
* Add the new entry to the code table.
*/
if (&state->dec_codetab[0] > free_entp || free_entp >= &state->dec_codetab[CSIZE]) {
cli_dbgmsg("%p <= %p, %p < %p(%ld)\n", &state->dec_codetab[0], free_entp, free_entp, &state->dec_codetab[CSIZE], CSIZE);
strm->msg = "full dictionary, cannot add new entry";
flags |= LZW_FLAG_FULLDICT;
ret = LZW_DICT_ERROR;
break;
}
free_entp->next = oldcodep;
free_entp->firstchar = free_entp->next->firstchar;
free_entp->length = free_entp->next->length+1;
free_entp->value = (codep < free_entp) ?
codep->firstchar : free_entp->firstchar;
free_entp++;
/* earlychange bit expansion */
if (echg && free_entp > maxcodep) {
if (++nbits > BITS_VALID) {
if (!cext)
nbits = BITS_VALID;
else if (nbits > BITS_MAX)
nbits = BITS_MAX;
}
nbitsmask = MAXCODE(nbits);
maxcodep = state->dec_codetab + nbitsmask-1;
}
if (free_code++ > CODE_VALID)
flags |= LZW_FLAG_EXTNCODEUSE;
oldcodep = codep;
} else
flags |= LZW_FLAG_FULLDICT;
if (code >= CODE_BASIC) {
/* check if code is valid */
if (code >= free_code) {
strm->msg = "cannot reference unpopulated dictionary entries";
flags |= LZW_FLAG_INVALIDCODE;
ret = LZW_DATA_ERROR;
break;
}
/*
* Code maps to a string, copy string
* value to output (written in reverse).
*/
if (codep->length > left) {
/*
* String is too long for decode buffer,
* locate portion that will fit, copy to
* the decode buffer, and setup restart
* logic for the next decoding call.
*/
state->dec_codep = codep;
do {
codep = codep->next;
} while (codep->length > left);
state->dec_restart = left;
to = wp = to + left;
do {
*--wp = codep->value;
codep = codep->next;
} while (--left);
goto inf_end;
}
to += codep->length, left -= codep->length;
wp = to;
do {
*--wp = codep->value;
codep = codep->next;
} while(codep != NULL);
} else
*to++ = code, left--;
}
inf_end:
/* restore state */
strm->next_out = to;
strm->avail_out = left;
strm->next_in = from;
strm->avail_in = have;
strm->flags = flags;
state->nbits = (uint16_t)nbits;
state->nextdata = nextdata;
state->nextbits = nextbits;
state->dec_nbitsmask = nbitsmask;
state->dec_oldcodep = oldcodep;
state->dec_free_entp = free_entp;
state->dec_maxcodep = maxcodep;
/* update state */
in -= strm->avail_in;
out -= strm->avail_out;
strm->total_in += in;
strm->total_out += out;
if ((in == 0 && out == 0) && ret == LZW_OK) {
strm->msg = "no data was processed";
ret = LZW_BUF_ERROR;
}
return ret;
}
int lzwInflateEnd(lzw_streamp strm)
{
free(strm->state->dec_codetab);
free(strm->state);
strm->state = NULL;
return LZW_OK;
}
static void code_print(code_t *code)
{
code_t *cpt = code;
uint8_t *string;
int i = 0;
string = cli_calloc(code->length+1, sizeof(uint8_t));
if (!string)
return;
while (cpt && (i < code->length)) {
if (isalnum(cpt->value))
string[code->length - i - 1] = cpt->value;
else
string[code->length - i - 1] = '*';
i++;
cpt = cpt->next;
}
printf("%s\n", string);
free(string);
}
static void dict_print(code_t *codetab, uint16_t start, uint16_t maxcode)
{
int i;
for (i = start; i < maxcode; i++) {
printf("%d: ", i);
code_print(codetab + i);
}
}