diff options
author | Rob Landley <rob@landley.net> | 2006-06-21 02:38:00 +0400 |
---|---|---|
committer | Rob Landley <rob@landley.net> | 2006-06-21 02:38:00 +0400 |
commit | b13fee4cbb98a20ae761da46b02b58cb47f289ab (patch) | |
tree | f7909ad87f1bc06d9d02c6589ae646a013d35558 /archival/libunarchive/decompress_unlzma.c | |
parent | 5483de1cb71b9cac095e4f6b65196b5390c06560 (diff) |
Since rangecoder is just a bunch of C functions, move it into the one user
(decompress_unlzma.c). Also a slight #include cleanup, and I've been meaning
to put #include <unistd.h> into libbb.h since it's so darn common...
Diffstat (limited to 'archival/libunarchive/decompress_unlzma.c')
-rw-r--r-- | archival/libunarchive/decompress_unlzma.c | 164 |
1 files changed, 144 insertions, 20 deletions
diff --git a/archival/libunarchive/decompress_unlzma.c b/archival/libunarchive/decompress_unlzma.c index fa7b37c37..10883581c 100644 --- a/archival/libunarchive/decompress_unlzma.c +++ b/archival/libunarchive/decompress_unlzma.c @@ -1,3 +1,4 @@ +/* vi:set ts=4: */ /* * Small lzma deflate implementation. * Copyright (C) 2006 Aurelien Jacobs <aurel@gnuage.org> @@ -5,31 +6,154 @@ * Based on LzmaDecode.c from the LZMA SDK 4.22 (http://www.7-zip.org/) * Copyright (C) 1999-2005 Igor Pavlov * - * This program 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 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 - * Lesser General Public License for more details. - * - * You should have received a copy of the GNU Lesser General Public - * License along with this library; if not, write to the Free Software - * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA + * Licensed under GPLv2 or later, see file LICENSE in this tarball for details. */ -#include <stdint.h> -#include <unistd.h> -#include <stdio.h> -#include <byteswap.h> - #include "libbb.h" - #include "unarchive.h" -#include "rangecoder.h" +#ifdef CONFIG_FEATURE_LZMA_FAST +# define speed_inline ATTRIBUTE_ALWAYS_INLINE +#else +# define speed_inline +#endif + + +typedef struct { + int fd; + uint8_t *ptr; + uint8_t *buffer; + uint8_t *buffer_end; + int buffer_size; + uint32_t code; + uint32_t range; + uint32_t bound; +} rc_t; + + +#define RC_TOP_BITS 24 +#define RC_MOVE_BITS 5 +#define RC_MODEL_TOTAL_BITS 11 + + +/* Called twice: once at startup and once in rc_normalize() */ +static void rc_read(rc_t * rc) +{ + rc->buffer_size = read(rc->fd, rc->buffer, rc->buffer_size); + if (rc->buffer_size <= 0) + bb_error_msg_and_die("unexpected EOF"); + rc->ptr = rc->buffer; + rc->buffer_end = rc->buffer + rc->buffer_size; +} + +/* Called once */ +static void rc_init(rc_t * rc, int fd, int buffer_size) +{ + int i; + + rc->fd = fd; + rc->buffer = xmalloc(buffer_size); + rc->buffer_size = buffer_size; + rc->buffer_end = rc->buffer + rc->buffer_size; + rc->ptr = rc->buffer_end; + + rc->code = 0; + rc->range = 0xFFFFFFFF; + for (i = 0; i < 5; i++) { + if (rc->ptr >= rc->buffer_end) + rc_read(rc); + rc->code = (rc->code << 8) | *rc->ptr++; + } +} + +/* Called once. TODO: bb_maybe_free() */ +static ATTRIBUTE_ALWAYS_INLINE void rc_free(rc_t * rc) +{ + if (ENABLE_FEATURE_CLEAN_UP) + free(rc->buffer); +} + +/* Called twice, but one callsite is in speed_inline'd rc_is_bit_0_helper() */ +static void rc_do_normalize(rc_t * rc) +{ + if (rc->ptr >= rc->buffer_end) + rc_read(rc); + rc->range <<= 8; + rc->code = (rc->code << 8) | *rc->ptr++; +} +static ATTRIBUTE_ALWAYS_INLINE void rc_normalize(rc_t * rc) +{ + if (rc->range < (1 << RC_TOP_BITS)) { + rc_do_normalize(rc); + } +} + +/* Called 9 times */ +/* Why rc_is_bit_0_helper exists? + * Because we want to always expose (rc->code < rc->bound) to optimizer + */ +static speed_inline uint32_t rc_is_bit_0_helper(rc_t * rc, uint16_t * p) +{ + rc_normalize(rc); + rc->bound = *p * (rc->range >> RC_MODEL_TOTAL_BITS); + return rc->bound; +} +static ATTRIBUTE_ALWAYS_INLINE int rc_is_bit_0(rc_t * rc, uint16_t * p) +{ + uint32_t t = rc_is_bit_0_helper(rc, p); + return rc->code < t; +} + +/* Called ~10 times, but very small, thus inlined */ +static speed_inline void rc_update_bit_0(rc_t * rc, uint16_t * p) +{ + rc->range = rc->bound; + *p += ((1 << RC_MODEL_TOTAL_BITS) - *p) >> RC_MOVE_BITS; +} +static speed_inline void rc_update_bit_1(rc_t * rc, uint16_t * p) +{ + rc->range -= rc->bound; + rc->code -= rc->bound; + *p -= *p >> RC_MOVE_BITS; +} + +/* Called 4 times in unlzma loop */ +static int rc_get_bit(rc_t * rc, uint16_t * p, int *symbol) +{ + if (rc_is_bit_0(rc, p)) { + rc_update_bit_0(rc, p); + *symbol *= 2; + return 0; + } else { + rc_update_bit_1(rc, p); + *symbol = *symbol * 2 + 1; + return 1; + } +} + +/* Called once */ +static ATTRIBUTE_ALWAYS_INLINE int rc_direct_bit(rc_t * rc) +{ + rc_normalize(rc); + rc->range >>= 1; + if (rc->code >= rc->range) { + rc->code -= rc->range; + return 1; + } + return 0; +} + +/* Called twice */ +static speed_inline void +rc_bit_tree_decode(rc_t * rc, uint16_t * p, int num_levels, int *symbol) +{ + int i = num_levels; + + *symbol = 1; + while (i--) + rc_get_bit(rc, p + *symbol, symbol); + *symbol -= 1 << num_levels; +} typedef struct { |