239 lines
7.6 KiB
C
239 lines
7.6 KiB
C
/*
|
|
SPDP code: SPDP is a unified compression/decompression algorithm that works
|
|
well on both binary 32-bit single-precision (float) and binary 64-bit double-
|
|
precision (double) floating-point data.
|
|
|
|
Copyright (c) 2016, Texas State University. All rights reserved.
|
|
|
|
Redistribution and use in source and binary forms, with or without modification,
|
|
are permitted for academic, research, experimental, or personal use provided
|
|
that the following conditions are met:
|
|
|
|
* Redistributions of source code must retain the above copyright notice,
|
|
this list of conditions, and the following disclaimer.
|
|
* Redistributions in binary form must reproduce the above copyright notice,
|
|
this list of conditions, and the following disclaimer in the documentation
|
|
and/or other materials provided with the distribution.
|
|
* Neither the name of Texas State University nor the names of its
|
|
contributors may be used to endorse or promote products derived from this
|
|
software without specific prior written permission.
|
|
|
|
For all other uses, please contact the Office for Commercialization and Industry
|
|
Relations at Texas State University <http://www.txstate.edu/ocir/>.
|
|
|
|
THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
|
|
ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
|
|
WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
|
|
DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR
|
|
ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
|
|
(INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
|
|
LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
|
|
ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
|
|
(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
|
|
SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
|
|
|
|
Authors: Martin Burtscher and Steven Claggett
|
|
*/
|
|
|
|
|
|
#include <stdlib.h>
|
|
#include <stdio.h>
|
|
#include <string.h>
|
|
|
|
#define MAX_TABLE_SIZE (1 << 18)
|
|
|
|
typedef unsigned char byte_t;
|
|
typedef unsigned int word_t;
|
|
|
|
|
|
static size_t spdp_compress(const byte_t level, const size_t length, byte_t* const buf1, byte_t* const buf2)
|
|
{
|
|
word_t* in = (word_t*)buf1;
|
|
word_t* out = (word_t*)buf2;
|
|
size_t len = length / sizeof(word_t);
|
|
|
|
word_t prev2 = 0;
|
|
word_t prev1 = 0;
|
|
size_t pos;
|
|
for (pos = 0; pos < len; pos++) {
|
|
word_t curr = in[pos];
|
|
out[pos] = curr - prev2;
|
|
prev2 = prev1;
|
|
prev1 = curr;
|
|
}
|
|
|
|
for (pos = len * sizeof(word_t); pos < length; pos++) {
|
|
buf2[pos] = buf1[pos];
|
|
}
|
|
|
|
byte_t prev = 0;
|
|
size_t wpos = 0;
|
|
size_t d;
|
|
for (d = 0; d < 8; d++) {
|
|
size_t rpos;
|
|
for (rpos = d; rpos < length; rpos += 8) {
|
|
byte_t curr = buf2[rpos];
|
|
buf1[wpos] = curr - prev;
|
|
prev = curr;
|
|
wpos++;
|
|
}
|
|
}
|
|
|
|
size_t predtabsize = 1 << (level + 9);
|
|
if (predtabsize > MAX_TABLE_SIZE) predtabsize = MAX_TABLE_SIZE;
|
|
const size_t predtabsizem1 = predtabsize - 1;
|
|
|
|
unsigned int lastpos[MAX_TABLE_SIZE];
|
|
memset(lastpos, 0, predtabsize * sizeof(unsigned int));
|
|
|
|
size_t rpos = 0;
|
|
wpos = 0;
|
|
unsigned int hist = 0;
|
|
while (rpos < length) {
|
|
byte_t val = buf1[rpos];
|
|
unsigned int lpos = lastpos[hist];
|
|
if (lpos >= 6) {
|
|
if ((buf1[lpos - 6] == buf1[rpos - 6]) && (buf1[lpos - 5] == buf1[rpos - 5]) &&
|
|
(buf1[lpos - 4] == buf1[rpos - 4]) && (buf1[lpos - 3] == buf1[rpos - 3]) &&
|
|
(buf1[lpos - 2] == buf1[rpos - 2]) && (buf1[lpos - 1] == buf1[rpos - 1])) {
|
|
byte_t cnt = 0;
|
|
while ((val == buf1[lpos]) && (cnt < 255) && (rpos < (length - 1))) {
|
|
lastpos[hist] = rpos;
|
|
hist = ((hist << 2) ^ val) & predtabsizem1;
|
|
rpos++;
|
|
lpos++;
|
|
cnt++;
|
|
val = buf1[rpos];
|
|
}
|
|
buf2[wpos] = cnt;
|
|
wpos++;
|
|
}
|
|
}
|
|
buf2[wpos] = val;
|
|
wpos++;
|
|
lastpos[hist] = rpos;
|
|
hist = ((hist << 2) ^ val) & predtabsizem1;
|
|
rpos++;
|
|
}
|
|
|
|
return wpos;
|
|
}
|
|
|
|
static void spdp_decompress(const byte_t level, const size_t length, byte_t* const buf2, byte_t* const buf1)
|
|
{
|
|
unsigned int predtabsize = 1 << (level + 9);
|
|
if (predtabsize > MAX_TABLE_SIZE) predtabsize = MAX_TABLE_SIZE;
|
|
const unsigned int predtabsizem1 = predtabsize - 1;
|
|
|
|
unsigned int lastpos[MAX_TABLE_SIZE];
|
|
memset(lastpos, 0, predtabsize * sizeof(unsigned int));
|
|
|
|
size_t rpos = 0;
|
|
size_t wpos = 0;
|
|
unsigned int hist = 0;
|
|
while (rpos < length) {
|
|
unsigned int lpos = lastpos[hist];
|
|
if (lpos >= 6) {
|
|
if ((buf1[lpos - 6] == buf1[wpos - 6]) && (buf1[lpos - 5] == buf1[wpos - 5]) &&
|
|
(buf1[lpos - 4] == buf1[wpos - 4]) && (buf1[lpos - 3] == buf1[wpos - 3]) &&
|
|
(buf1[lpos - 2] == buf1[wpos - 2]) && (buf1[lpos - 1] == buf1[wpos - 1])) {
|
|
byte_t cnt = buf2[rpos];
|
|
rpos++;
|
|
byte_t j;
|
|
for (j = 0; j < cnt; j++) {
|
|
byte_t val = buf1[wpos] = buf1[lpos];
|
|
lastpos[hist] = wpos;
|
|
hist = ((hist << 2) ^ val) & predtabsizem1;
|
|
wpos++;
|
|
lpos++;
|
|
}
|
|
}
|
|
}
|
|
byte_t val = buf1[wpos] = buf2[rpos];
|
|
lastpos[hist] = wpos;
|
|
hist = ((hist << 2) ^ val) & predtabsizem1;
|
|
wpos++;
|
|
rpos++;
|
|
}
|
|
const size_t usize = wpos;
|
|
|
|
byte_t val = 0;
|
|
rpos = 0;
|
|
size_t d;
|
|
for (d = 0; d < 8; d++) {
|
|
size_t wpos;
|
|
for (wpos = d; wpos < usize; wpos += 8) {
|
|
val += buf1[rpos];
|
|
buf2[wpos] = val;
|
|
rpos++;
|
|
}
|
|
}
|
|
|
|
word_t* in = (word_t*)buf2;
|
|
word_t* out = (word_t*)buf1;
|
|
const size_t len = usize / sizeof(word_t);
|
|
|
|
word_t prev2 = 0;
|
|
word_t prev1 = 0;
|
|
size_t pos;
|
|
for (pos = 0; pos < len; pos++) {
|
|
word_t curr = in[pos] + prev2;
|
|
out[pos] = curr;
|
|
prev2 = prev1;
|
|
prev1 = curr;
|
|
}
|
|
for (pos = len * sizeof(word_t); pos < usize; pos++) {
|
|
buf1[pos] = buf2[pos];
|
|
}
|
|
}
|
|
#ifndef NMAIN
|
|
#define BUFFER_SIZE (1 << 23)
|
|
static byte_t buffer1[BUFFER_SIZE];
|
|
static byte_t buffer2[BUFFER_SIZE * 2 + 9];
|
|
int main(int argc, char *argv[])
|
|
{
|
|
fprintf(stderr, "SPDP Floating-Point Compressor v1.0\n");
|
|
fprintf(stderr, "Copyright (c) 2016 Texas State University\n\n");
|
|
|
|
if ((argc != 1) && (argc != 2)) {
|
|
fprintf(stderr, "compression usage: %s level < uncompressed_file > compressed_file\n", argv[0]);
|
|
fprintf(stderr, "decompression usage: %s < compressed_file > decompressed_file\n", argv[0]);
|
|
return -1;
|
|
}
|
|
|
|
if (argc == 2) { // compression
|
|
byte_t level = atoi(argv[1]);
|
|
if (level < 0) level = 0;
|
|
if (level > 9) level = 9;
|
|
fwrite(&level, sizeof(byte_t), 1, stdout);
|
|
|
|
int length = fread(buffer1, sizeof(byte_t), BUFFER_SIZE, stdin);
|
|
while (length > 0) {
|
|
fwrite(&length, sizeof(int), 1, stdout);
|
|
int csize = compress(level, length, buffer1, buffer2);
|
|
fwrite(&csize, sizeof(int), 1, stdout);
|
|
fwrite(buffer2, sizeof(byte_t), csize, stdout);
|
|
length = fread(buffer1, sizeof(byte_t), BUFFER_SIZE, stdin);
|
|
}
|
|
} else { // decompression
|
|
byte_t level = 10;
|
|
fread(&level, sizeof(byte_t), 1, stdin);
|
|
if ((level < 0) || (level > 9)) {
|
|
fprintf(stderr, "incorrect input file type\n");
|
|
return -2;
|
|
}
|
|
|
|
int length;
|
|
while (fread(&length, sizeof(int), 1, stdin) > 0) {
|
|
int csize;
|
|
fread(&csize, sizeof(int), 1, stdin);
|
|
fread(buffer2, sizeof(byte_t), csize, stdin);
|
|
decompress(level, csize, buffer2, buffer1);
|
|
fwrite(buffer1, sizeof(byte_t), length, stdout);
|
|
}
|
|
}
|
|
|
|
return 0;
|
|
}
|
|
#endif
|