From 3b34851de1eaf358cf9268922fa0eeed8278d680 Mon Sep 17 00:00:00 2001 From: Lasse Collin Date: Thu, 28 Aug 2008 22:53:15 +0300 Subject: Sort of garbage collection commit. :-| Many things are still broken. API has changed a lot and it will still change a little more here and there. The command line tool doesn't have all the required changes to reflect the API changes, so it's easy to get "internal error" or trigger assertions. --- src/liblzma/delta/Makefile.am | 34 +++++++++++ src/liblzma/delta/delta_common.c | 66 +++++++++++++++++++++ src/liblzma/delta/delta_common.h | 44 ++++++++++++++ src/liblzma/delta/delta_decoder.c | 82 ++++++++++++++++++++++++++ src/liblzma/delta/delta_decoder.h | 32 ++++++++++ src/liblzma/delta/delta_encoder.c | 119 ++++++++++++++++++++++++++++++++++++++ src/liblzma/delta/delta_encoder.h | 30 ++++++++++ 7 files changed, 407 insertions(+) create mode 100644 src/liblzma/delta/Makefile.am create mode 100644 src/liblzma/delta/delta_common.c create mode 100644 src/liblzma/delta/delta_common.h create mode 100644 src/liblzma/delta/delta_decoder.c create mode 100644 src/liblzma/delta/delta_decoder.h create mode 100644 src/liblzma/delta/delta_encoder.c create mode 100644 src/liblzma/delta/delta_encoder.h (limited to 'src/liblzma/delta') diff --git a/src/liblzma/delta/Makefile.am b/src/liblzma/delta/Makefile.am new file mode 100644 index 00000000..fc09f5b8 --- /dev/null +++ b/src/liblzma/delta/Makefile.am @@ -0,0 +1,34 @@ +## +## Copyright (C) 2008 Lasse Collin +## +## This library is free software; you can redistribute it and/or +## modify it under the terms of the GNU Lesser General Public +## License as published by the Free Software Foundation; either +## version 2.1 of the License, or (at your option) any later version. +## +## This library 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 +## Lesser General Public License for more details. +## + +noinst_LTLIBRARIES = libdelta.la +libdelta_la_CPPFLAGS = \ + -I@top_srcdir@/src/liblzma/api \ + -I@top_srcdir@/src/liblzma/common + +libdelta_la_SOURCES = \ + delta_common.c \ + delta_common.h + +if COND_ENCODER_DELTA +libdelta_la_SOURCES += \ + delta_encoder.c \ + delta_encoder.h +endif + +if COND_DECODER_DELTA +libdelta_la_SOURCES += \ + delta_decoder.c \ + delta_decoder.h +endif diff --git a/src/liblzma/delta/delta_common.c b/src/liblzma/delta/delta_common.c new file mode 100644 index 00000000..d40e0c7f --- /dev/null +++ b/src/liblzma/delta/delta_common.c @@ -0,0 +1,66 @@ +/////////////////////////////////////////////////////////////////////////////// +// +/// \file delta_common.c +/// \brief Common stuff for Delta encoder and decoder +// +// Copyright (C) 2007 Lasse Collin +// +// This library is free software; you can redistribute it and/or +// modify it under the terms of the GNU Lesser General Public +// License as published by the Free Software Foundation; either +// version 2.1 of the License, or (at your option) any later version. +// +// This library 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 +// Lesser General Public License for more details. +// +/////////////////////////////////////////////////////////////////////////////// + +#include "delta_common.h" + + +static void +delta_coder_end(lzma_coder *coder, lzma_allocator *allocator) +{ + lzma_next_end(&coder->next, allocator); + lzma_free(coder, allocator); + return; +} + + +extern lzma_ret +lzma_delta_coder_init(lzma_next_coder *next, lzma_allocator *allocator, + const lzma_filter_info *filters, lzma_code_function code) +{ + // Allocate memory for the decoder if needed. + if (next->coder == NULL) { + next->coder = lzma_alloc(sizeof(lzma_coder), allocator); + if (next->coder == NULL) + return LZMA_MEM_ERROR; + + // End function is the same for encoder and decoder. + next->end = &delta_coder_end; + next->coder->next = LZMA_NEXT_CODER_INIT; + } + + // Coding function is different for encoder and decoder. + next->code = code; + + // Set the delta distance. + if (filters[0].options == NULL) + return LZMA_PROG_ERROR; + next->coder->distance = ((lzma_options_delta *)(filters[0].options)) + ->distance; + if (next->coder->distance < LZMA_DELTA_DISTANCE_MIN + || next->coder->distance > LZMA_DELTA_DISTANCE_MAX) + return LZMA_HEADER_ERROR; + + // Initialize the rest of the variables. + next->coder->pos = 0; + memzero(next->coder->history, LZMA_DELTA_DISTANCE_MAX); + + // Initialize the next decoder in the chain, if any. + return lzma_next_filter_init(&next->coder->next, + allocator, filters + 1); +} diff --git a/src/liblzma/delta/delta_common.h b/src/liblzma/delta/delta_common.h new file mode 100644 index 00000000..1d58899d --- /dev/null +++ b/src/liblzma/delta/delta_common.h @@ -0,0 +1,44 @@ +/////////////////////////////////////////////////////////////////////////////// +// +/// \file delta_common.h +/// \brief Common stuff for Delta encoder and decoder +// +// Copyright (C) 2007 Lasse Collin +// +// This library is free software; you can redistribute it and/or +// modify it under the terms of the GNU Lesser General Public +// License as published by the Free Software Foundation; either +// version 2.1 of the License, or (at your option) any later version. +// +// This library 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 +// Lesser General Public License for more details. +// +/////////////////////////////////////////////////////////////////////////////// + +#ifndef LZMA_DELTA_COMMON_H +#define LZMA_DELTA_COMMON_H + +#include "common.h" + +struct lzma_coder_s { + /// Next coder in the chain + lzma_next_coder next; + + /// Delta distance + size_t distance; + + /// Position in history[] + uint8_t pos; + + /// Buffer to hold history of the original data + uint8_t history[LZMA_DELTA_DISTANCE_MAX]; +}; + + +extern lzma_ret lzma_delta_coder_init( + lzma_next_coder *next, lzma_allocator *allocator, + const lzma_filter_info *filters, lzma_code_function code); + +#endif diff --git a/src/liblzma/delta/delta_decoder.c b/src/liblzma/delta/delta_decoder.c new file mode 100644 index 00000000..ee22ba02 --- /dev/null +++ b/src/liblzma/delta/delta_decoder.c @@ -0,0 +1,82 @@ +/////////////////////////////////////////////////////////////////////////////// +// +/// \file delta_decoder.c +/// \brief Delta filter decoder +// +// Copyright (C) 2007, 2008 Lasse Collin +// +// This library is free software; you can redistribute it and/or +// modify it under the terms of the GNU Lesser General Public +// License as published by the Free Software Foundation; either +// version 2.1 of the License, or (at your option) any later version. +// +// This library 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 +// Lesser General Public License for more details. +// +/////////////////////////////////////////////////////////////////////////////// + +#include "delta_decoder.h" +#include "delta_common.h" + + +static void +decode_buffer(lzma_coder *coder, uint8_t *buffer, size_t size) +{ + const size_t distance = coder->distance; + + for (size_t i = 0; i < size; ++i) { + buffer[i] += coder->history[(distance + coder->pos) & 0xFF]; + coder->history[coder->pos-- & 0xFF] = buffer[i]; + } +} + + +static lzma_ret +delta_decode(lzma_coder *coder, lzma_allocator *allocator, + const uint8_t *restrict in, size_t *restrict in_pos, + size_t in_size, uint8_t *restrict out, + size_t *restrict out_pos, size_t out_size, lzma_action action) +{ + assert(coder->next.code != NULL); + + const size_t out_start = *out_pos; + + const lzma_ret ret = coder->next.code(coder->next.coder, allocator, + in, in_pos, in_size, out, out_pos, out_size, + action); + + decode_buffer(coder, out + out_start, *out_pos - out_start); + + return ret; +} + + +extern lzma_ret +lzma_delta_decoder_init(lzma_next_coder *next, lzma_allocator *allocator, + const lzma_filter_info *filters) +{ + return lzma_delta_coder_init(next, allocator, filters, &delta_decode); +} + + +extern lzma_ret +lzma_delta_props_decode(void **options, lzma_allocator *allocator, + const uint8_t *props, size_t props_size) +{ + if (props_size != 1) + return LZMA_HEADER_ERROR; + + lzma_options_delta *opt + = lzma_alloc(sizeof(lzma_options_delta), allocator); + if (opt == NULL) + return LZMA_MEM_ERROR; + + opt->type = LZMA_DELTA_TYPE_BYTE; + opt->distance = props[0] + 1; + + *options = opt; + + return LZMA_OK; +} diff --git a/src/liblzma/delta/delta_decoder.h b/src/liblzma/delta/delta_decoder.h new file mode 100644 index 00000000..84852bf3 --- /dev/null +++ b/src/liblzma/delta/delta_decoder.h @@ -0,0 +1,32 @@ +/////////////////////////////////////////////////////////////////////////////// +// +/// \file delta_decoder.h +/// \brief Delta filter decoder +// +// Copyright (C) 2007 Lasse Collin +// +// This library is free software; you can redistribute it and/or +// modify it under the terms of the GNU Lesser General Public +// License as published by the Free Software Foundation; either +// version 2.1 of the License, or (at your option) any later version. +// +// This library 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 +// Lesser General Public License for more details. +// +/////////////////////////////////////////////////////////////////////////////// + +#ifndef LZMA_DELTA_DECODER_H +#define LZMA_DELTA_DECODER_H + +#include "common.h" + +extern lzma_ret lzma_delta_decoder_init(lzma_next_coder *next, + lzma_allocator *allocator, const lzma_filter_info *filters); + +extern lzma_ret lzma_delta_props_decode( + void **options, lzma_allocator *allocator, + const uint8_t *props, size_t props_size); + +#endif diff --git a/src/liblzma/delta/delta_encoder.c b/src/liblzma/delta/delta_encoder.c new file mode 100644 index 00000000..d8f40287 --- /dev/null +++ b/src/liblzma/delta/delta_encoder.c @@ -0,0 +1,119 @@ +/////////////////////////////////////////////////////////////////////////////// +// +/// \file delta_encoder.c +/// \brief Delta filter encoder +// +// Copyright (C) 2007, 2008 Lasse Collin +// +// This library is free software; you can redistribute it and/or +// modify it under the terms of the GNU Lesser General Public +// License as published by the Free Software Foundation; either +// version 2.1 of the License, or (at your option) any later version. +// +// This library 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 +// Lesser General Public License for more details. +// +/////////////////////////////////////////////////////////////////////////////// + +#include "delta_encoder.h" +#include "delta_common.h" + + +/// Copies and encodes the data at the same time. This is used when Delta +/// is the first filter in the chain (and thus the last filter in the +/// encoder's filter stack). +static void +copy_and_encode(lzma_coder *coder, + const uint8_t *restrict in, uint8_t *restrict out, size_t size) +{ + const size_t distance = coder->distance; + + for (size_t i = 0; i < size; ++i) { + const uint8_t tmp = coder->history[ + (distance + coder->pos) & 0xFF]; + coder->history[coder->pos-- & 0xFF] = in[i]; + out[i] = in[i] - tmp; + } +} + + +/// Encodes the data in place. This is used when we are the last filter +/// in the chain (and thus non-last filter in the encoder's filter stack). +static void +encode_in_place(lzma_coder *coder, uint8_t *buffer, size_t size) +{ + const size_t distance = coder->distance; + + for (size_t i = 0; i < size; ++i) { + const uint8_t tmp = coder->history[ + (distance + coder->pos) & 0xFF]; + coder->history[coder->pos-- & 0xFF] = buffer[i]; + buffer[i] -= tmp; + } +} + + +static lzma_ret +delta_encode(lzma_coder *coder, lzma_allocator *allocator, + const uint8_t *restrict in, size_t *restrict in_pos, + size_t in_size, uint8_t *restrict out, + size_t *restrict out_pos, size_t out_size, lzma_action action) +{ + lzma_ret ret; + + if (coder->next.code == NULL) { + const size_t in_avail = in_size - *in_pos; + const size_t out_avail = out_size - *out_pos; + const size_t size = MIN(in_avail, out_avail); + + copy_and_encode(coder, in + *in_pos, out + *out_pos, size); + + *in_pos += size; + *out_pos += size; + + ret = action != LZMA_RUN && *in_pos == in_size + ? LZMA_STREAM_END : LZMA_OK; + + } else { + const size_t out_start = *out_pos; + + ret = coder->next.code(coder->next.coder, allocator, + in, in_pos, in_size, out, out_pos, out_size, + action); + + encode_in_place(coder, out + out_start, *out_pos - out_start); + } + + return ret; +} + + +extern lzma_ret +lzma_delta_encoder_init(lzma_next_coder *next, lzma_allocator *allocator, + const lzma_filter_info *filters) +{ + return lzma_delta_coder_init(next, allocator, filters, &delta_encode); +} + + +extern lzma_ret +lzma_delta_props_encode(const void *options, uint8_t *out) +{ + if (options == NULL) + return LZMA_PROG_ERROR; + + const lzma_options_delta *opt = options; + + // It's possible that newer liblzma versions will support larger + // distance values. + if (opt->type != LZMA_DELTA_TYPE_BYTE + || opt->distance < LZMA_DELTA_DISTANCE_MIN + || opt->distance > LZMA_DELTA_DISTANCE_MAX) + return LZMA_HEADER_ERROR; + + out[0] = opt->distance - LZMA_DELTA_DISTANCE_MIN; + + return LZMA_OK; +} diff --git a/src/liblzma/delta/delta_encoder.h b/src/liblzma/delta/delta_encoder.h new file mode 100644 index 00000000..b8b29c61 --- /dev/null +++ b/src/liblzma/delta/delta_encoder.h @@ -0,0 +1,30 @@ +/////////////////////////////////////////////////////////////////////////////// +// +/// \file delta_encoder.h +/// \brief Delta filter encoder +// +// Copyright (C) 2007 Lasse Collin +// +// This library is free software; you can redistribute it and/or +// modify it under the terms of the GNU Lesser General Public +// License as published by the Free Software Foundation; either +// version 2.1 of the License, or (at your option) any later version. +// +// This library 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 +// Lesser General Public License for more details. +// +/////////////////////////////////////////////////////////////////////////////// + +#ifndef LZMA_DELTA_ENCODER_H +#define LZMA_DELTA_ENCODER_H + +#include "common.h" + +extern lzma_ret lzma_delta_encoder_init(lzma_next_coder *next, + lzma_allocator *allocator, const lzma_filter_info *filters); + +extern lzma_ret lzma_delta_props_encode(const void *options, uint8_t *out); + +#endif -- cgit v1.2.3