+++ /dev/null
-#include "tosthread.h"
-#include "tosthread_amradio.h"
-#include "tosthread_amserial.h"
-#include "tosthread_leds.h"
-#include "tosthread_threadsync.h"
-#include "tosthread_logstorage.h"
-#include "StorageVolumes.h"
-#include "lz.c"
-#include "lz.h"
-
-#define SENDING_PERIOD 1
-#define AM_SENSOR_DATA_MSG 0x25
-#define NUM_RECORDS_TO_COMPRESS 50
-
-//Data structure for storing sensor data
-typedef nx_struct sensor_data {
- nx_uint32_t seq_no;
- nx_uint16_t hum;
- nx_uint16_t temp;
- nx_uint16_t tsr;
- nx_uint16_t par;
-} sensor_data_t;
-
-typedef nx_struct radio_data {
- nx_uint8_t taskNum;
- nx_uint16_t pktNum;
- nx_uint8_t more;
- nx_uint8_t data[0];
-} radio_data_t;
-
-typedef struct log_entry {
- uint8_t taskNum;
- uint16_t pktNum;
- uint8_t more;
- uint8_t srcNodeId;
- uint8_t len;
- uint8_t data[TOSH_DATA_LENGTH - sizeof(radio_data_t)];
-} log_entry_t;
-
-//Initialize variables associated with each thread
-tosthread_t receive_handler;
-tosthread_t decompress_handler;
-
-mutex_t log_mutex;
-
-void receive_thread(void* arg);
-void decompress_thread(void* arg);
-
-void tosthread_main(void* arg) {
- mutex_init(&log_mutex);
- amRadioStart();
-amSerialStart();
- led0Toggle();
- volumeLogErase(VOLUME_SENSORLOG);
- volumeLogSeek(VOLUME_SENSORLOG, SEEK_BEGINNING);
- led0Toggle();
- tosthread_create(&receive_handler, receive_thread, NULL, 1000);
- tosthread_create(&decompress_handler, decompress_thread, NULL, 5000);
-}
-
-void receive_thread(void* arg) {
- message_t mesg;
- log_entry_t entry;
- bool data_lost;
- uint8_t payload_len;
- storage_len_t entry_len;
- radio_data_t *payload;
-
- for (;;) {
- if (amRadioReceive(&mesg, 0, AM_SENSOR_DATA_MSG) == SUCCESS) {
- payload_len = radioGetPayloadLength(&mesg);
- payload = (radio_data_t *)radioGetPayload(&mesg, payload_len);
-
- entry.taskNum = payload->taskNum;
- entry.pktNum = payload->pktNum;
- entry.more = payload->more;
- entry.srcNodeId = amRadioGetSource(&mesg) & 0xFF;
- entry.len = payload_len - sizeof(radio_data_t);
- memcpy(entry.data, payload->data, entry.len);
-
-/*
- {
- int i;
- for (i = 0; i < entry.len; i++) {
- entry.data[i] = payload->data[i];
- }
- }
-*/
-
- entry_len = sizeof(log_entry_t);
- mutex_lock(&log_mutex);
- while( volumeLogAppend(VOLUME_SENSORLOG, &entry, &entry_len, &data_lost) != SUCCESS );
- mutex_unlock(&log_mutex);
- }
- }
-}
-
-void decompress_thread(void* arg) {
- storage_len_t entry_len;
- log_entry_t entry;
- uint16_t insize[2] = {0, 0};
- uint8_t taskNum[2] = {0, 0};
- uint16_t pktNum[2] = {0, 0};
- uint8_t in[2][((NUM_RECORDS_TO_COMPRESS * sizeof(sensor_data_t) * 257 - 1) / 256) + 1 + 1];
- uint8_t out[NUM_RECORDS_TO_COMPRESS * sizeof(sensor_data_t)];
-// uint32_t pktLoss[2] = {0, 0};
- bool isComplete[2];
-
- for(;;) {
- tosthread_sleep(SENDING_PERIOD);
-
- while( volumeLogCurrentReadOffset(VOLUME_SENSORLOG) != volumeLogCurrentWriteOffset(VOLUME_SENSORLOG) ) {
- entry_len = sizeof(log_entry_t);
- mutex_lock(&log_mutex);
- while( volumeLogRead(VOLUME_SENSORLOG, &entry, &entry_len) != SUCCESS );
- mutex_unlock(&log_mutex);
-
- if (entry.pktNum == 0) {
- led2Toggle();
-
- taskNum[entry.srcNodeId] = entry.taskNum;
- pktNum[entry.srcNodeId] = 1;
- isComplete[entry.srcNodeId] = TRUE;
- memcpy(in[entry.srcNodeId], entry.data, entry.len);
- insize[entry.srcNodeId] = entry.len;
- } else {
- led0Toggle();
- if (entry.taskNum == taskNum[entry.srcNodeId] && entry.pktNum == pktNum[entry.srcNodeId]) {
-// uint16_t startIndex = (TOSH_DATA_LENGTH - sizeof(radio_data_t)) * pktNum[entry.srcNodeId];
-// memcpy(&(in[entry.srcNodeId][startIndex]), entry.data, entry.len);
-// memcpy(&(in[entry.srcNodeId][insize[entry.srcNodeId] - 1]), entry.data, entry.len);
-
- {
- int i;
- for (i = 0; i < entry.len; i++) {
- (in[entry.srcNodeId])[insize[entry.srcNodeId] + i] = entry.data[i];
- }
- }
-
- insize[entry.srcNodeId] += entry.len;
- pktNum[entry.srcNodeId]++;
-
- if (entry.more == FALSE && isComplete[entry.srcNodeId] == TRUE) {
- led1Toggle();
-
- LZ_Uncompress(in[entry.srcNodeId], out, insize[entry.srcNodeId]);
-
-/*
- {
- int tempinsize = insize[entry.srcNodeId], sendSize = 0, sendIndex = 0;
- void *serialMsg_payload;
- message_t serialMsg;
-
- while (tempinsize > 0) {
- if (tempinsize > TOSH_DATA_LENGTH) {
- sendSize = TOSH_DATA_LENGTH;
- } else {
- sendSize = tempinsize;
- }
-
- serialMsg_payload = serialGetPayload(&serialMsg, sendSize);
- memcpy(serialMsg_payload, &(in[entry.srcNodeId][sendIndex]), sendSize);
- while( amSerialSend(AM_BROADCAST_ADDR, &serialMsg, sendSize, 0) != SUCCESS );
- sendIndex += sendSize;
- tempinsize -= sendSize;
- }
- }
-*/
-/*
- {
- int i;
- for (i = 0; i < NUM_RECORDS_TO_COMPRESS; i++) {
- message_t serialMsg;
- void *serialMsg_payload = serialGetPayload(&serialMsg, sizeof(sensor_data_t));
- memcpy(serialMsg_payload, &(out[i * sizeof(sensor_data_t)]), sizeof(sensor_data_t));
- while( amSerialSend(AM_BROADCAST_ADDR, &serialMsg, sizeof(sensor_data_t), 0) != SUCCESS );
- }
- }
-*/
- pktNum[entry.srcNodeId] = 0;
- }
- } else {
- isComplete[entry.srcNodeId] = FALSE;
- led0Toggle();
- }
- }
- }
- }
-}
+++ /dev/null
-#include "tosthread.h"
-#include "tosthread_amradio.h"
-#include "tosthread_leds.h"
-#include "tosthread_threadsync.h"
-#include "tosthread_logstorage.h"
-#include "tmote_onboard_sensors.h"
-#include "StorageVolumes.h"
-#include "lz.c"
-#include "lz.h"
-
-#define SAMPLING_PERIOD 100
-#define SENDING_PERIOD 50
-#define SENDING_INTERVAL 25
-#define AM_SENSOR_DATA_MSG 0x25
-#define NUM_RECORDS_TO_COMPRESS 50
-#define NUM_SENSORS 4
-#define TOTAL_NUM_RECORDS_TO_SEND 500
-
-//Data structure for storing sensor data
-typedef nx_struct sensor_data {
- nx_uint32_t seq_no;
- nx_uint16_t hum;
- nx_uint16_t temp;
- nx_uint16_t tsr;
- nx_uint16_t par;
-} sensor_data_t;
-
-typedef nx_struct radio_data {
- nx_uint8_t taskNum;
- nx_uint16_t pktNum;
- nx_uint8_t more;
- nx_uint8_t data[0];
-} radio_data_t;
-
-//Initialize variables associated with each thread
-tosthread_t humidity;
-tosthread_t temperature;
-tosthread_t total_solar;
-tosthread_t photo_active;
-tosthread_t store_handler;
-tosthread_t send_handler;
-
-message_t send_msg;
-sensor_data_t storing_sensor_data;
-mutex_t data_mutex;
-mutex_t log_mutex;
-barrier_t send_barrier;
-barrier_t sense_barrier;
-
-sensor_data_t compressing_sensor_data[NUM_RECORDS_TO_COMPRESS];
-
-void humidity_thread(void* arg);
-void temperature_thread(void* arg);
-void total_solar_thread(void* arg);
-void photo_active_thread(void* arg);
-void store_thread(void* arg);
-void send_thread(void* arg);
-
-void tosthread_main(void* arg) {
- mutex_init(&data_mutex);
- mutex_init(&log_mutex);
- barrier_reset(&send_barrier, NUM_SENSORS+1);
- barrier_reset(&sense_barrier, NUM_SENSORS+1);
-
- storing_sensor_data.seq_no = 0;
-
- amRadioStart();
- led0Toggle();
- volumeLogErase(VOLUME_SENSORLOG);
- volumeLogSeek(VOLUME_SENSORLOG, SEEK_BEGINNING);
- led0Toggle();
- tosthread_create(&humidity, humidity_thread, NULL, 200);
- tosthread_create(&temperature, temperature_thread, NULL, 200);
- tosthread_create(&total_solar, total_solar_thread, NULL, 200);
- tosthread_create(&photo_active, photo_active_thread, NULL, 200);
- tosthread_create(&store_handler, store_thread, NULL, 200);
- tosthread_create(&send_handler, send_thread, NULL, 5000);
-}
-
-void read_sensor(error_t (*read)(uint16_t*), nx_uint16_t* nx_val) {
- uint16_t val;
- for(;;) {
- (*read)(&val);
- mutex_lock(&data_mutex);
- *nx_val = val;
- mutex_unlock(&data_mutex);
- barrier_block(&send_barrier);
- barrier_block(&sense_barrier);
- }
-}
-
-void humidity_thread(void* arg) {
- read_sensor(sensirionSht11_humidity_read, &(storing_sensor_data.hum));
-}
-void temperature_thread(void* arg) {
- read_sensor(sensirionSht11_temperature_read, &(storing_sensor_data.temp));
-}
-void total_solar_thread(void* arg) {
- read_sensor(hamamatsuS10871_tsr_read, &(storing_sensor_data.tsr));
-}
-void photo_active_thread(void* arg) {
- read_sensor(hamamatsuS1087_par_read, &(storing_sensor_data.par));
-}
-void store_thread(void* arg) {
- storage_len_t sensor_data_len;
- bool sensor_records_lost;
-
- for(;;) {
- barrier_block(&send_barrier);
- barrier_reset(&send_barrier, NUM_SENSORS + 1);
-
- mutex_lock(&log_mutex);
- sensor_data_len = sizeof(sensor_data_t);
- while( volumeLogAppend(VOLUME_SENSORLOG, &storing_sensor_data, &sensor_data_len, &sensor_records_lost) != SUCCESS );
- mutex_unlock(&log_mutex);
-
- storing_sensor_data.seq_no++;
- led0Toggle();
-
- //tosthread_sleep(SAMPLING_PERIOD);
- barrier_block(&sense_barrier);
- barrier_reset(&sense_barrier, NUM_SENSORS + 1);
- }
-}
-
-uint8_t taskNum = 0;
-
-void send_thread(void* arg) {
- storage_len_t sensor_data_len;
- uint8_t numRecords = 0;
- uint8_t out[((NUM_RECORDS_TO_COMPRESS * sizeof(sensor_data_t) * 257 - 1) / 256) + 1 + 1];
-
- for(;;) {
- tosthread_sleep(SENDING_PERIOD);
-
- while( volumeLogCurrentReadOffset(VOLUME_SENSORLOG) != volumeLogCurrentWriteOffset(VOLUME_SENSORLOG) ) {
- sensor_data_len = sizeof(sensor_data_t);
- mutex_lock(&log_mutex);
- while( volumeLogRead(VOLUME_SENSORLOG, &(compressing_sensor_data[numRecords]), &sensor_data_len) != SUCCESS );
- numRecords++;
- mutex_unlock(&log_mutex);
-
- if (numRecords == NUM_RECORDS_TO_COMPRESS) {
- uint8_t pktNum = 0;
- uint16_t outsize = 0, sendsize = 0, sendindex = 0;
- radio_data_t *payload = NULL;
-
- outsize = LZ_Compress((void *)compressing_sensor_data, out, NUM_RECORDS_TO_COMPRESS * sizeof(sensor_data_t));
-
- while (outsize > 0) {
- if (outsize > (TOSH_DATA_LENGTH - sizeof(radio_data_t))) {
- sendsize = TOSH_DATA_LENGTH - sizeof(radio_data_t);
- } else {
- sendsize = outsize;
- }
-
- payload = (radio_data_t *) radioGetPayload(&send_msg, sizeof(radio_data_t) + sendsize);
- payload->taskNum = taskNum;
- payload->pktNum = pktNum;
- payload->more = ((outsize - sendsize) > 0) ? TRUE : FALSE;
- memcpy(payload->data, &(out[sendindex]), sendsize);
-
- while( amRadioSend(AM_BROADCAST_ADDR, &send_msg, sizeof(radio_data_t) + sendsize, AM_SENSOR_DATA_MSG) != SUCCESS );
-
- outsize -= sendsize;
- sendindex += sendsize;
- pktNum++;
- led1Toggle();
- tosthread_sleep(SENDING_INTERVAL);
- }
-
- taskNum++;
- pktNum = 0;
- numRecords = 0;
- }
- }
-
- //led2Toggle();
- }
-}
+++ /dev/null
-/*************************************************************************
-* Name: lz.c
-* Author: Marcus Geelnard
-* Description: LZ77 coder/decoder implementation.
-* Reentrant: Yes
-*
-* The LZ77 compression scheme is a substitutional compression scheme
-* proposed by Abraham Lempel and Jakob Ziv in 1977. It is very simple in
-* its design, and uses no fancy bit level compression.
-*
-* This is my first attempt at an implementation of a LZ77 code/decoder.
-*
-* The principle of the LZ77 compression algorithm is to store repeated
-* occurrences of strings as references to previous occurrences of the same
-* string. The point is that the reference consumes less space than the
-* string itself, provided that the string is long enough (in this
-* implementation, the string has to be at least 4 bytes long, since the
-* minimum coded reference is 3 bytes long). Also note that the term
-* "string" refers to any kind of byte sequence (it does not have to be
-* an ASCII string, for instance).
-*
-* The coder uses a brute force approach to finding string matches in the
-* history buffer (or "sliding window", if you wish), which is very, very
-* slow. I recon the complexity is somewhere between O(n^2) and O(n^3),
-* depending on the input data.
-*
-* There is also a faster implementation that uses a large working buffer
-* in which a "jump table" is stored, which is used to quickly find
-* possible string matches (see the source code for LZ_CompressFast() for
-* more information). The faster method is an order of magnitude faster,
-* but still quite slow compared to other compression methods.
-*
-* The upside is that decompression is very fast, and the compression ratio
-* is often very good.
-*
-* The reference to a string is coded as a (length,offset) pair, where the
-* length indicates the length of the string, and the offset gives the
-* offset from the current data position. To distinguish between string
-* references and literal strings (uncompressed bytes), a string reference
-* is preceded by a marker byte, which is chosen as the least common byte
-* symbol in the input data stream (this marker byte is stored in the
-* output stream as the first byte).
-*
-* Occurrences of the marker byte in the stream are encoded as the marker
-* byte followed by a zero byte, which means that occurrences of the marker
-* byte have to be coded with two bytes.
-*
-* The lengths and offsets are coded in a variable length fashion, allowing
-* values of any magnitude (up to 4294967295 in this implementation).
-*
-* With this compression scheme, the worst case compression result is
-* (257/256)*insize + 1.
-*
-*-------------------------------------------------------------------------
-* Copyright (c) 2003-2006 Marcus Geelnard
-*
-* This software is provided 'as-is', without any express or implied
-* warranty. In no event will the authors be held liable for any damages
-* arising from the use of this software.
-*
-* Permission is granted to anyone to use this software for any purpose,
-* including commercial applications, and to alter it and redistribute it
-* freely, subject to the following restrictions:
-*
-* 1. The origin of this software must not be misrepresented; you must not
-* claim that you wrote the original software. If you use this software
-* in a product, an acknowledgment in the product documentation would
-* be appreciated but is not required.
-*
-* 2. Altered source versions must be plainly marked as such, and must not
-* be misrepresented as being the original software.
-*
-* 3. This notice may not be removed or altered from any source
-* distribution.
-*
-* Marcus Geelnard
-* marcus.geelnard at home.se
-*************************************************************************/
-
-
-/*************************************************************************
-* Constants used for LZ77 coding
-*************************************************************************/
-
-/* Maximum offset (can be any size < 2^31). Lower values give faster
- compression, while higher values gives better compression. The default
- value of 100000 is quite high. Experiment to see what works best for
- you. */
-#define LZ_MAX_OFFSET 100000
-
-
-
-/*************************************************************************
-* INTERNAL FUNCTIONS *
-*************************************************************************/
-
-
-/*************************************************************************
-* _LZ_StringCompare() - Return maximum length string match.
-*************************************************************************/
-
-static uint32_t _LZ_StringCompare( unsigned char * str1,
- unsigned char * str2, uint32_t minlen, uint32_t maxlen )
-{
- uint32_t len;
-
- for( len = minlen; (len < maxlen) && (str1[len] == str2[len]); ++ len );
-
- return len;
-}
-
-
-/*************************************************************************
-* _LZ_WriteVarSize() - Write uint32_teger with variable number of
-* bytes depending on value.
-*************************************************************************/
-
-static int _LZ_WriteVarSize( uint32_t x, unsigned char * buf )
-{
- uint32_t y;
- int num_bytes, i, b;
-
- /* Determine number of bytes needed to store the number x */
- y = x >> 3;
- for( num_bytes = 5; num_bytes >= 2; -- num_bytes )
- {
- if( y & 0xfe000000 ) break;
- y <<= 7;
- }
-
- /* Write all bytes, seven bits in each, with 8:th bit set for all */
- /* but the last byte. */
- for( i = num_bytes-1; i >= 0; -- i )
- {
- b = (x >> (i*7)) & 0x0000007f;
- if( i > 0 )
- {
- b |= 0x00000080;
- }
- *buf ++ = (unsigned char) b;
- }
-
- /* Return number of bytes written */
- return num_bytes;
-}
-
-
-/*************************************************************************
-* _LZ_ReadVarSize() - Read uint32_teger with variable number of
-* bytes depending on value.
-*************************************************************************/
-
-static int _LZ_ReadVarSize( uint32_t * x, unsigned char * buf )
-{
- uint32_t y, b, num_bytes;
-
- /* Read complete value (stop when byte contains zero in 8:th bit) */
- y = 0;
- num_bytes = 0;
- do
- {
- b = (uint32_t) (*buf ++);
- y = (y << 7) | (b & 0x0000007f);
- ++ num_bytes;
- }
- while( b & 0x00000080 );
-
- /* Store value in x */
- *x = y;
-
- /* Return number of bytes read */
- return num_bytes;
-}
-
-
-
-/*************************************************************************
-* PUBLIC FUNCTIONS *
-*************************************************************************/
-
-
-/*************************************************************************
-* LZ_Compress() - Compress a block of data using an LZ77 coder.
-* in - Input (uncompressed) buffer.
-* out - Output (compressed) buffer. This buffer must be 0.4% larger
-* than the input buffer, plus one byte.
-* insize - Number of input bytes.
-* The function returns the size of the compressed data.
-*************************************************************************/
-
-int LZ_Compress( unsigned char *in, unsigned char *out,
- uint32_t insize )
-{
- unsigned char marker, symbol;
- uint32_t inpos, outpos, bytesleft, i;
- uint32_t maxoffset, offset, bestoffset;
- uint32_t maxlength, length, bestlength;
- uint32_t histogram[ 256 ];
- unsigned char *ptr1, *ptr2;
-
- /* Do we have anything to compress? */
- if( insize < 1 )
- {
- return 0;
- }
-
- /* Create histogram */
- for( i = 0; i < 256; ++ i )
- {
- histogram[ i ] = 0;
- }
- for( i = 0; i < insize; ++ i )
- {
- ++ histogram[ in[ i ] ];
- }
-
- /* Find the least common byte, and use it as the marker symbol */
- marker = 0;
- for( i = 1; i < 256; ++ i )
- {
- if( histogram[ i ] < histogram[ marker ] )
- {
- marker = i;
- }
- }
-
- /* Remember the marker symbol for the decoder */
- out[ 0 ] = marker;
-
- /* Start of compression */
- inpos = 0;
- outpos = 1;
-
- /* Main compression loop */
- bytesleft = insize;
- do
- {
- /* Determine most distant position */
- if( inpos > LZ_MAX_OFFSET ) {
- maxoffset = LZ_MAX_OFFSET;
- }
- else {
- maxoffset = inpos;
- }
-
- /* Get pointer to current position */
- ptr1 = &in[ inpos ];
-
- /* Search history window for maximum length string match */
- bestlength = 3;
- bestoffset = 0;
- for( offset = 3; offset <= maxoffset; ++ offset )
- {
- /* Get pointer to candidate string */
- ptr2 = &ptr1[ -(int)offset ];
-
- /* Quickly determine if this is a candidate (for speed) */
- if( (ptr1[ 0 ] == ptr2[ 0 ]) &&
- (ptr1[ bestlength ] == ptr2[ bestlength ]) )
- {
- /* Determine maximum length for this offset */
- maxlength = (bytesleft < offset ? bytesleft : offset);
-
- /* Count maximum length match at this offset */
- length = _LZ_StringCompare( ptr1, ptr2, 0, maxlength );
-
- /* Better match than any previous match? */
- if( length > bestlength )
- {
- bestlength = length;
- bestoffset = offset;
- }
- }
- }
-
- /* Was there a good enough match? */
- if( (bestlength >= 8) ||
- ((bestlength == 4) && (bestoffset <= 0x0000007f)) ||
- ((bestlength == 5) && (bestoffset <= 0x00003fff)) ||
- ((bestlength == 6) && (bestoffset <= 0x001fffff)) ||
- ((bestlength == 7) && (bestoffset <= 0x0fffffff)) )
- {
- out[ outpos ++ ] = (unsigned char) marker;
- outpos += _LZ_WriteVarSize( bestlength, &out[ outpos ] );
- outpos += _LZ_WriteVarSize( bestoffset, &out[ outpos ] );
- inpos += bestlength;
- bytesleft -= bestlength;
- }
- else
- {
- /* Output single byte (or two bytes if marker byte) */
- symbol = in[ inpos ++ ];
- out[ outpos ++ ] = symbol;
- if( symbol == marker )
- {
- out[ outpos ++ ] = 0;
- }
- -- bytesleft;
- }
- }
- while( bytesleft > 3 );
-
- /* Dump remaining bytes, if any */
- while( inpos < insize )
- {
- if( in[ inpos ] == marker )
- {
- out[ outpos ++ ] = marker;
- out[ outpos ++ ] = 0;
- }
- else
- {
- out[ outpos ++ ] = in[ inpos ];
- }
- ++ inpos;
- }
-
- return outpos;
-}
-
-
-/*************************************************************************
-* LZ_CompressFast() - Compress a block of data using an LZ77 coder.
-* in - Input (uncompressed) buffer.
-* out - Output (compressed) buffer. This buffer must be 0.4% larger
-* than the input buffer, plus one byte.
-* insize - Number of input bytes.
-* work - Pointer to a temporary buffer (internal working buffer), which
-* must be able to hold (insize+65536) uint32_tegers.
-* The function returns the size of the compressed data.
-*************************************************************************/
-
-int LZ_CompressFast( unsigned char *in, unsigned char *out,
- uint32_t insize, uint32_t *work )
-{
- unsigned char marker, symbol;
- uint32_t inpos, outpos, bytesleft, i, index, symbols;
- uint32_t offset, bestoffset;
- uint32_t maxlength, length, bestlength;
- uint32_t histogram[ 256 ], *lastindex, *jumptable;
- unsigned char *ptr1, *ptr2;
-
- /* Do we have anything to compress? */
- if( insize < 1 )
- {
- return 0;
- }
-
- /* Assign arrays to the working area */
- lastindex = work;
- jumptable = &work[ 65536 ];
-
- /* Build a "jump table". Here is how the jump table works:
- jumptable[i] points to the nearest previous occurrence of the same
- symbol pair as in[i]:in[i+1], so in[i] == in[jumptable[i]] and
- in[i+1] == in[jumptable[i]+1], and so on... Following the jump table
- gives a dramatic boost for the string search'n'match loop compared
- to doing a brute force search. The jump table is built in O(n) time,
- so it is a cheap operation in terms of time, but it is expensice in
- terms of memory consumption. */
- for( i = 0; i < 65536; ++ i )
- {
- lastindex[ i ] = 0xffffffff;
- }
- for( i = 0; i < insize-1; ++ i )
- {
- symbols = (((uint32_t)in[i]) << 8) | ((uint32_t)in[i+1]);
- index = lastindex[ symbols ];
- lastindex[ symbols ] = i;
- jumptable[ i ] = index;
- }
- jumptable[ insize-1 ] = 0xffffffff;
-
- /* Create histogram */
- for( i = 0; i < 256; ++ i )
- {
- histogram[ i ] = 0;
- }
- for( i = 0; i < insize; ++ i )
- {
- ++ histogram[ in[ i ] ];
- }
-
- /* Find the least common byte, and use it as the marker symbol */
- marker = 0;
- for( i = 1; i < 256; ++ i )
- {
- if( histogram[ i ] < histogram[ marker ] )
- {
- marker = i;
- }
- }
-
- /* Remember the marker symbol for the decoder */
- out[ 0 ] = marker;
-
- /* Start of compression */
- inpos = 0;
- outpos = 1;
-
- /* Main compression loop */
- bytesleft = insize;
- do
- {
- /* Get pointer to current position */
- ptr1 = &in[ inpos ];
-
- /* Search history window for maximum length string match */
- bestlength = 3;
- bestoffset = 0;
- index = jumptable[ inpos ];
- while( (index != 0xffffffff) && ((inpos - index) < LZ_MAX_OFFSET) )
- {
- /* Get pointer to candidate string */
- ptr2 = &in[ index ];
-
- /* Quickly determine if this is a candidate (for speed) */
- if( ptr2[ bestlength ] == ptr1[ bestlength ] )
- {
- /* Determine maximum length for this offset */
- offset = inpos - index;
- maxlength = (bytesleft < offset ? bytesleft : offset);
-
- /* Count maximum length match at this offset */
- length = _LZ_StringCompare( ptr1, ptr2, 2, maxlength );
-
- /* Better match than any previous match? */
- if( length > bestlength )
- {
- bestlength = length;
- bestoffset = offset;
- }
- }
-
- /* Get next possible index from jump table */
- index = jumptable[ index ];
- }
-
- /* Was there a good enough match? */
- if( (bestlength >= 8) ||
- ((bestlength == 4) && (bestoffset <= 0x0000007f)) ||
- ((bestlength == 5) && (bestoffset <= 0x00003fff)) ||
- ((bestlength == 6) && (bestoffset <= 0x001fffff)) ||
- ((bestlength == 7) && (bestoffset <= 0x0fffffff)) )
- {
- out[ outpos ++ ] = (unsigned char) marker;
- outpos += _LZ_WriteVarSize( bestlength, &out[ outpos ] );
- outpos += _LZ_WriteVarSize( bestoffset, &out[ outpos ] );
- inpos += bestlength;
- bytesleft -= bestlength;
- }
- else
- {
- /* Output single byte (or two bytes if marker byte) */
- symbol = in[ inpos ++ ];
- out[ outpos ++ ] = symbol;
- if( symbol == marker )
- {
- out[ outpos ++ ] = 0;
- }
- -- bytesleft;
- }
- }
- while( bytesleft > 3 );
-
- /* Dump remaining bytes, if any */
- while( inpos < insize )
- {
- if( in[ inpos ] == marker )
- {
- out[ outpos ++ ] = marker;
- out[ outpos ++ ] = 0;
- }
- else
- {
- out[ outpos ++ ] = in[ inpos ];
- }
- ++ inpos;
- }
-
- return outpos;
-}
-
-
-/*************************************************************************
-* LZ_Uncompress() - Uncompress a block of data using an LZ77 decoder.
-* in - Input (compressed) buffer.
-* out - Output (uncompressed) buffer. This buffer must be large
-* enough to hold the uncompressed data.
-* insize - Number of input bytes.
-*************************************************************************/
-
-void LZ_Uncompress( unsigned char *in, unsigned char *out,
- uint32_t insize )
-{
- unsigned char marker, symbol;
- uint32_t i, inpos, outpos, length, offset;
-
- /* Do we have anything to uncompress? */
- if( insize < 1 )
- {
- return;
- }
-
- /* Get marker symbol from input stream */
- marker = in[ 0 ];
- inpos = 1;
-
- /* Main decompression loop */
- outpos = 0;
- do
- {
- symbol = in[ inpos ++ ];
- if( symbol == marker )
- {
- /* We had a marker byte */
- if( in[ inpos ] == 0 )
- {
- /* It was a single occurrence of the marker byte */
- out[ outpos ++ ] = marker;
- ++ inpos;
- }
- else
- {
- /* Extract true length and offset */
- inpos += _LZ_ReadVarSize( &length, &in[ inpos ] );
- inpos += _LZ_ReadVarSize( &offset, &in[ inpos ] );
-
- /* Copy corresponding data from history window */
- for( i = 0; i < length; ++ i )
- {
- out[ outpos ] = out[ outpos - offset ];
- ++ outpos;
- }
- }
- }
- else
- {
- /* No marker, plain copy */
- out[ outpos ++ ] = symbol;
- }
- }
- while( inpos < insize );
-}
projects / tinyos-2.x.git / commitdiff