WebSVN – ipe_artfile_utils – Blame – /trunk/ipe32_lzw_decoder.c

Rev	Author	Line No.	Line
2	daniel-mar	1	/**
		2	* LZW Decoder for Imagination Pilots Entertainment 32-bit games (IPE32)
		3	* - Where's Waldo? Exploring Geography
		4	* - Eraser Turnabout by Imagination Pilots
		5	* - Virtual K'Nex by Imagination Pilots
		6	* ART file packer and unpacker by Daniel Marschall, ViaThinkSoft (C) 2018
		7	* Revision: 2018-02-15
		8	*
		9	* Based on : Basic LZW Data Compression program published in DDJ October 1989 issue.
		10	* by Mark R. Nelson
		11	* http://collaboration.cmc.ec.gc.ca/science/rpn/biblio/ddj/Website/articles/DDJ/1989/8910/8910b/8910b.htm
		12	* Updated by: Shawn M. Regan, January 1990
		13	* http://mirror.bagelwood.com/textfiles/computers/regan.lst
		14	* Updated by: Daniel Marschall, 11 February 2018
		15	* https://misc.daniel-marschall.de/code/c/lzw.c
		16	* Changed for IPE32: - Simplified
		17	* - Thread safe
		18	* - MAX_BITS = 13
		19	**/
		20
		21	#include <stdio.h>
		22	#include <stdlib.h>
		23	#include <stdint.h>
		24
		25	#include "utils.h"
		26	#include "ipe32_lzw_decoder.h"
		27
		28	#define INIT_BITS 9
		29	#define MAX_BITS 13 /* Do not exceed 14 with this program */
		30
		31	#if MAX_BITS == 14 /* Set the table size. Must be a prime */
		32	#define TABLE_SIZE 18041 /* number somewhat larger than 2^MAX_BITS.*/
		33	#elif MAX_BITS == 13
		34	#define TABLE_SIZE 9029
		35	#else
		36	#define TABLE_SIZE 5021
		37	#endif
		38
		39	#define CLEAR_TABLE 256 /* Code to flush the string table */
		40	#define TERMINATOR 257 /* To mark EOF Condition, instead of MAX_VALUE */
		41	#define FIRST_CODE 258 /* First available code for code_value table */
		42
		43	#define MAXVAL(n) (( 1 <<( n )) -1) /* max_value formula macro */
		44
		45	unsigned char* decode_string(Ipe32LZWDecoder decoder, unsigned char buffer, unsigned int code) {
		46	int i=0;
		47
		48	while (code > 255) {
		49	*buffer++ = decoder->append_character[code];
		50	code = decoder->prefix_code[code];
		51	if (i++ >= 4000) {
		52	// printf("Error during code expansion\n");
		53	return NULL;
		54	}
		55	}
		56	*buffer=code;
		57	return(buffer);
		58	}
		59
		60	unsigned input_code(Ipe32LZWDecoder decoder, unsigned char lzwInputBuffer, int* inputBufferPos) {
		61	unsigned int return_value;
		62
		63	while (decoder->input_bit_count <= 24) {
		64	decoder->input_bit_buffer \|= lzwInputBuffer[(*inputBufferPos)] << (24 - decoder->input_bit_count);
		65	(*inputBufferPos)++;
		66	decoder->input_bit_count += 8;
		67	}
		68	return_value=decoder->input_bit_buffer >> (32-decoder->num_bits);
		69	decoder->input_bit_buffer <<= decoder->num_bits;
		70	decoder->input_bit_count -= decoder->num_bits;
		71	return(return_value);
		72	}
		73
		74	void reset_input_buffer(Ipe32LZWDecoder *decoder) {
		75	decoder->input_bit_count = 0;
		76	decoder->input_bit_buffer = 0;
		77	}
		78
		79	void ipe32lzw_reset_decoder(Ipe32LZWDecoder *decoder) {
		80	decoder->num_bits = INIT_BITS;
		81	decoder->max_code = MAXVAL(decoder->num_bits); /* Initialize max_value & max_code */
		82
		83	// Make sure the input buffer is correctly flushed
		84	reset_input_buffer(decoder);
		85	}
		86
		87	void ipe32lzw_init_decoder(Ipe32LZWDecoder *decoder) {
		88	decoder->prefix_code = malloc(TABLE_SIZE*sizeof(unsigned int));
		89	decoder->append_character = malloc(TABLE_SIZE*sizeof(unsigned char));
		90	ipe32lzw_reset_decoder(decoder);
		91	}
		92
		93	// Returns: Bytes written or -1 when an error occurs
		94	int ipe32lzw_decode(Ipe32LZWDecoder decoder, unsigned char outputBuffer, const size_t outpufBufferSize, unsigned char* lzwInputBuffer, const size_t maxReadBytes) {
		95	unsigned int next_code=FIRST_CODE;
		96	unsigned int new_code;
		97	unsigned int old_code;
		98	int character;
		99	int clear_flag=1; /* Need to clear the code value array */
		100	unsigned char *string;
		101
		102	int inputBufferPos = 0;
		103	int outputBufferPos = 0;
		104	#define OUTPUT(code) { if (outputBufferPos == outpufBufferSize) return -1; outputBuffer[outputBufferPos++] = code; }
		105
		106	ipe32lzw_reset_decoder(decoder);
		107
		108	while (1) {
		109	if (inputBufferPos == maxReadBytes) return -1;
		110	if ((new_code=input_code(decoder, lzwInputBuffer, &inputBufferPos)) == TERMINATOR) break;
		111
		112	if (clear_flag) { /* Initialize or Re-Initialize */
		113	clear_flag=0;
		114	old_code=new_code; /* The next three lines have been moved */
		115	character=old_code; /* from the original */
		116	OUTPUT(old_code);
		117	continue;
		118	}
		119	if (new_code == CLEAR_TABLE) { /* Clear string table */
		120	clear_flag=1;
		121	decoder->num_bits=INIT_BITS;
		122	next_code=FIRST_CODE;
		123	decoder->max_code = MAXVAL(decoder->num_bits);
		124	continue;
		125	}
		126	if (new_code >= next_code) { /* Check for string+char+string */
		127	*decoder->decode_stack=character;
		128	string = decode_string(decoder, decoder->decode_stack+1,old_code);
		129	} else {
		130	string = decode_string(decoder, decoder->decode_stack,new_code);
		131	}
		132	if (string == NULL) return -1;
		133
		134	character = string; / Output decoded string in reverse */
		135	while (string >= decoder->decode_stack) {
		136	OUTPUT(*string--);
		137	}
		138
		139	if (next_code <= decoder->max_code) { /* Add to string table if not full */
		140	decoder->prefix_code[next_code]=old_code;
		141	decoder->append_character[next_code++]=character;
		142	if (next_code == decoder->max_code && decoder->num_bits < MAX_BITS) {
		143	decoder->max_code = MAXVAL(++decoder->num_bits);
		144	}
		145	}
		146	old_code=new_code;
		147	}
		148
		149	return outputBufferPos;
		150	}
		151
		152	void ipe32lzw_free_decoder(Ipe32LZWDecoder *decoder) {
		153	free(decoder->prefix_code);
		154	free(decoder->append_character);
		155	}
		156
		157	Ipe32LZWDecoder* new_ipe32lzw_decoder(void) {
		158	return (Ipe32LZWDecoder*)app_zero_alloc(sizeof(Ipe32LZWDecoder));
		159	}

Subversion Repositories ipe_artfile_utils

ipe_artfile_utils/trunk/ipe32_lzw_decoder.c – Rev 2