306 lines
7.7 KiB
C
306 lines
7.7 KiB
C
/*
|
|
* Basic implementation of LZ78 compression algorithm
|
|
*
|
|
* Copyright (C) 2010 evilaliv3 <giovanni.pellerano@evilaliv3.org>
|
|
*
|
|
* This program is free software: you can redistribute it and/or modify
|
|
* it under the terms of the GNU General Public License as published by
|
|
* the Free Software Foundation, either version 3 of the License, or
|
|
* (at your option) any later version.
|
|
*
|
|
* 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, see <http://www.gnu.org/licenses/>.
|
|
*/
|
|
|
|
#include <stdlib.h>
|
|
#include <unistd.h>
|
|
#include <errno.h>
|
|
#include <string.h>
|
|
|
|
#include "bitio.h"
|
|
|
|
/* Struct of bitfile */
|
|
struct __bit_file {
|
|
int fd; /* File descriptor */
|
|
int mode; /* Mode: read 0, write 1 */
|
|
UINTMAX_T buff_size; /* Buffer size (bits) */
|
|
UINTMAX_T w_start; /* Window start (bits) */
|
|
UINTMAX_T w_len; /* Window length (bits) */
|
|
char buff[1]; /* Buffer (contiguous memory area) */
|
|
};
|
|
|
|
/* Return max value that can be represented using UINTMAX_T */
|
|
UINTMAX_T max_index() {
|
|
UINTMAX_T max = -1;
|
|
max /= 8;
|
|
return max;
|
|
}
|
|
|
|
bit_file* bit_open(int fd, int mode, UINTMAX_T buff_size) {
|
|
|
|
bit_file* bfp;
|
|
int ret;
|
|
|
|
if (mode != ACCESS_READ && mode != ACCESS_WRITE)
|
|
return NULL;
|
|
|
|
if (mode == ACCESS_READ)
|
|
ret = read(fd, NULL, 0);
|
|
else /* mode == ACCESS_WRITE */
|
|
ret = write(fd, NULL, 0);
|
|
|
|
if(ret != 0)
|
|
return NULL;
|
|
|
|
if (buff_size % 8 != 0)
|
|
return NULL;
|
|
|
|
buff_size = (buff_size > max_index()) ? max_index() : buff_size;
|
|
|
|
/* Buffer allocation */
|
|
bfp = (bit_file*) calloc(1, sizeof(bit_file) + buff_size / 8);
|
|
if (bfp == NULL) {
|
|
close(fd);
|
|
} else {
|
|
bfp->fd = fd;
|
|
bfp->mode = mode;
|
|
bfp->buff_size = buff_size;
|
|
/* bfp->w_start and bfp->w_len are initialized by calloc */
|
|
}
|
|
|
|
return bfp;
|
|
}
|
|
|
|
int bit_read(bit_file* bfp, char* buff_out, UINTMAX_T n_bits, uint8_t ofs) {
|
|
uint8_t* base;
|
|
uint8_t mask;
|
|
uint8_t r_mask;
|
|
uint8_t writebit;
|
|
const uint8_t* readptr;
|
|
UINTMAX_T buff_ready_bytes;
|
|
UINTMAX_T bits_read = 0;
|
|
UINTMAX_T bits_read_total = 0;
|
|
UINTMAX_T buff_size;
|
|
UINTMAX_T w_start;
|
|
UINTMAX_T w_len;
|
|
UINTMAX_T c;
|
|
uint8_t aligned;
|
|
|
|
if (bfp == NULL || buff_out == NULL || ofs > 7)
|
|
return -1;
|
|
|
|
if (bfp->mode != ACCESS_READ)
|
|
return -1;
|
|
|
|
buff_size = bfp->buff_size;
|
|
w_start = bfp->w_start;
|
|
w_len = bfp->w_len;
|
|
|
|
mask = 1 << ofs;
|
|
base = (uint8_t*) buff_out;
|
|
|
|
/* Check if input ad output are aligned to byte */
|
|
aligned = (mask == 1 && (w_start % 8 == 0)) ? 1 : 0;
|
|
|
|
while (n_bits > 0) {
|
|
/* Buffer refill if needed */
|
|
if (w_len == 0) {
|
|
c = read(bfp->fd, bfp->buff, buff_size / 8);
|
|
if (c == (uint32_t)-1) {
|
|
if (errno == EAGAIN) {
|
|
errno = 0;
|
|
break;
|
|
} else {
|
|
return -1;
|
|
}
|
|
} else if (c == 0) {
|
|
break;
|
|
}
|
|
|
|
w_start = 0;
|
|
w_len = c * 8;
|
|
}
|
|
|
|
readptr = (uint8_t*)&(bfp->buff) + w_start / 8;
|
|
|
|
if (aligned && w_len > 7 && n_bits >= w_len) {
|
|
/* Optimization: due to alignment we can use memcpy */
|
|
buff_ready_bytes = w_len / 8;
|
|
memcpy(base, readptr, buff_ready_bytes);
|
|
base += buff_ready_bytes;
|
|
|
|
bits_read = buff_ready_bytes * 8;
|
|
w_start = (w_start + bits_read) % buff_size;
|
|
w_len -= bits_read;
|
|
n_bits -= bits_read;
|
|
bits_read_total += bits_read;
|
|
} else {
|
|
/* Single bit read */
|
|
r_mask = 1 << w_start % 8;
|
|
|
|
writebit = (*readptr & r_mask) ? 1 : 0;
|
|
if (writebit == 0) {
|
|
*base &= ~mask;
|
|
} else {
|
|
*base |= mask;
|
|
}
|
|
|
|
w_start = ((w_start + 1) % buff_size);
|
|
--w_len;
|
|
--n_bits;
|
|
++bits_read_total;
|
|
|
|
if (mask == 0x80) {
|
|
mask = 1;
|
|
++base;
|
|
aligned = (mask == 1 && (w_start % 8 == 0)) ? 1 : 0;
|
|
} else {
|
|
mask <<= 1;
|
|
}
|
|
}
|
|
}
|
|
|
|
/* Update */
|
|
bfp->buff_size = buff_size;
|
|
bfp->w_start = w_start;
|
|
bfp->w_len = w_len;
|
|
|
|
return bits_read_total;
|
|
}
|
|
|
|
int bit_write(bit_file* bfp, const char* buff_in, UINTMAX_T n_bits, uint8_t ofs) {
|
|
UINTMAX_T ret = 0;
|
|
const uint8_t* base;
|
|
uint8_t mask;
|
|
uint8_t readbit;
|
|
uint8_t* writeptr;
|
|
UINTMAX_T pos;
|
|
UINTMAX_T buff_free_bits;
|
|
UINTMAX_T buff_free_bytes;
|
|
UINTMAX_T bits_written = 0;
|
|
uint8_t aligned;
|
|
|
|
if (bfp == NULL || buff_in == NULL || ofs > 7)
|
|
return -1;
|
|
|
|
if (bfp->mode != ACCESS_WRITE)
|
|
return -1;
|
|
|
|
mask = 1 << ofs;
|
|
base = (uint8_t*)buff_in;
|
|
|
|
pos = bfp->w_start + bfp->w_len;
|
|
buff_free_bits = bfp->buff_size - bfp->w_len;
|
|
|
|
/* Check if input ad output are aligned to byte */
|
|
aligned = (mask == 1 && (pos % 8 == 0)) ? 1 : 0;
|
|
|
|
while (n_bits > 0) {
|
|
writeptr = (uint8_t*)&(bfp->buff) + pos / 8;
|
|
|
|
if (aligned && buff_free_bits > 7 && n_bits >= buff_free_bits) {
|
|
/* Optimization: due to alignment we can use memcpy */
|
|
buff_free_bytes = buff_free_bits / 8;
|
|
memcpy(writeptr, base, buff_free_bytes);
|
|
base += buff_free_bytes;
|
|
bits_written = buff_free_bytes * 8;
|
|
|
|
pos += bits_written;
|
|
bfp->w_len += bits_written;
|
|
n_bits -= bits_written;
|
|
ret += bits_written;
|
|
buff_free_bits -= bits_written;
|
|
} else {
|
|
/* Single bit write */
|
|
readbit = (*base & mask) ? 1 : 0;
|
|
if (readbit == 0) {
|
|
*writeptr &= ~(1 << pos % 8);
|
|
} else {
|
|
*writeptr |= (1 << pos % 8);
|
|
}
|
|
|
|
if (mask == 0x80) {
|
|
mask = 1;
|
|
++base;
|
|
aligned = (mask == 1 && (pos % 8 == 0)) ? 1 : 0;
|
|
} else {
|
|
mask <<= 1;
|
|
}
|
|
|
|
++pos;
|
|
++(bfp->w_len);
|
|
--(n_bits);
|
|
--buff_free_bits;
|
|
++ret;
|
|
}
|
|
|
|
/* Flush if needed */
|
|
if (bfp->w_len == bfp->buff_size) {
|
|
if (bit_flush(bfp) == -1)
|
|
return -1;
|
|
if (bfp->w_len != 0)
|
|
return ret;
|
|
pos = bfp->w_start + bfp->w_len;
|
|
buff_free_bits = bfp->buff_size;
|
|
}
|
|
|
|
}
|
|
|
|
return ret;
|
|
}
|
|
|
|
int bit_flush(bit_file* bfp) {
|
|
UINTMAX_T count;
|
|
UINTMAX_T written;
|
|
UINTMAX_T n;
|
|
uint8_t* base;
|
|
|
|
if (bfp == NULL)
|
|
return -1;
|
|
|
|
count = bfp->w_len / 8;
|
|
written = 0;
|
|
base = (uint8_t*) bfp->buff + bfp->w_start / 8;
|
|
|
|
while (count > 0) {
|
|
n = write(bfp->fd, base, count);
|
|
if (n == (uint32_t)-1) {
|
|
if (errno == EAGAIN) {
|
|
errno = 0;
|
|
break;
|
|
} else {
|
|
return -1;
|
|
}
|
|
}
|
|
base += n;
|
|
written += n;
|
|
count -= n;
|
|
}
|
|
|
|
bfp->w_start = (bfp->w_start + written * 8) % bfp->buff_size;
|
|
bfp->w_len -= written * 8;
|
|
return 0;
|
|
}
|
|
|
|
int bit_close(bit_file* bfp) {
|
|
int fd;
|
|
|
|
if (bfp == NULL)
|
|
return -1;
|
|
|
|
fd = bfp->fd;
|
|
|
|
if (bfp->w_len % 8)
|
|
bfp->w_len += 8 - (bfp->w_len % 8);
|
|
|
|
bit_flush(bfp);
|
|
free(bfp);
|
|
close(fd);
|
|
return 0;
|
|
}
|