Rev 7 | Blame | Compare with Previous | Last modification | View Log | RSS feed
/*
* Copyright (c) 2002-2006 The TenDRA Project <http://www.tendra.org/>.
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions are met:
*
* 1. Redistributions of source code must retain the above copyright notice,
* this list of conditions and the following disclaimer.
* 2. 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.
* 3. Neither the name of The TenDRA Project nor the names of its contributors
* may be used to endorse or promote products derived from this software
* without specific, prior written permission.
*
* 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 HOLDERS 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.
*
* $Id$
*/
/*
Crown Copyright (c) 1997
This TenDRA(r) Computer Program is subject to Copyright
owned by the United Kingdom Secretary of State for Defence
acting through the Defence Evaluation and Research Agency
(DERA). It is made available to Recipients with a
royalty-free licence for its use, reproduction, transfer
to other parties and amendment for any purpose not excluding
product development provided that any such use et cetera
shall be deemed to be acceptance of the following conditions:-
(1) Its Recipients shall ensure that this Notice is
reproduced upon any copies or amended versions of it;
(2) Any amended version of it shall be clearly marked to
show both the nature of and the organisation responsible
for the relevant amendment or amendments;
(3) Its onward transfer from a recipient to another
party shall be deemed to be that party's acceptance of
these conditions;
(4) DERA gives no warranty or assurance as to its
quality or suitability for any purpose and DERA accepts
no liability whatsoever in relation to any use to which
it may be put.
*/
#include "config.h"
#include <limits.h>
#include "c_types.h"
#include "error.h"
#include "char.h"
#include "encode.h"
#include "literal.h"
#include "ustring.h"
#include "xalloc.h"
/*
DUMP A BITSTREAM TO A FILE
This routine dumps the contents of the bitstream bs to its associated
file. The contents will be lost if this is the null file. Any odd
bits will remain in the bitstream.
*/
static void
dump_bitstream(BITSTREAM *bs)
{
size_t n = (size_t)bs->bytes;
if (n) {
string t = bs->text;
FILE *f = bs->file;
if (f) {
IGNORE fwrite((gen_ptr)t, sizeof(character), n, f);
}
t[0] = t[n];
}
bs->bytes = 0;
return;
}
/*
LIST OF FREE BITSTREAMS
This variable gives the list of bitstreams from which new bitstreams
are allocated.
*/
static BITSTREAM *free_bitstreams = NULL;
/*
CREATE A NEW BITSTREAM
This routine creates a new bitstream with associated file f and
linkage lnk.
*/
BITSTREAM *
start_bitstream(FILE *f, gen_ptr lnk)
{
BITSTREAM *bs = free_bitstreams;
if (bs) {
free_bitstreams = bs->prev;
} else {
bs = xmalloc_one(BITSTREAM);
bs->text = xustr((gen_size)CHUNK_SIZE);
}
bs->bytes = 0;
bs->bits = 0;
bs->size = 0;
bs->file = f;
bs->link = lnk;
bs->prev = NULL;
return (bs);
}
/*
END A BITSTREAM
This routine frees the bitstream bs including clearing the buffer
for any file bitstream if w is true.
*/
void
end_bitstream(BITSTREAM *bs, int w)
{
BITSTREAM *ps = bs;
if (w && ps->file) {
/* Align bitstream and dump */
ps = enc_boundary(ps);
dump_bitstream(ps);
}
while (ps->prev) {
ps = ps->prev;
}
ps->prev = free_bitstreams;
free_bitstreams = bs;
return;
}
/*
EXTEND A BITSTREAM
This routine extends the bitstream bs by dumping its contents to a
file or linking it to a fresh chunk.
*/
static BITSTREAM *
extend_bitstream(BITSTREAM *bs)
{
bs->bytes = CHUNK_SIZE;
bs->bits = 0;
if (bs->file) {
dump_bitstream(bs);
} else {
BITSTREAM *ps = start_bitstream(NIL(FILE), bs->link);
ps->prev = bs;
bs = ps;
}
return (bs);
}
/*
ADD A NUMBER OF BITS TO A BITSTREAM
This routine adds the n bits given by d to the bitstream bs. n will
always be at most 16.
*/
BITSTREAM *
enc_bits(BITSTREAM *bs, unsigned n, unsigned d)
{
if (n) {
unsigned long b = (unsigned long)d;
string text = bs->text;
unsigned bytes = bs->bytes;
unsigned bits = bs->bits;
if (bits) {
/* Add existing bits */
unsigned r = (BYTE_SIZE - bits);
unsigned long c = (unsigned long)text[bytes];
b |= ((c >> r) << n);
n += bits;
}
bits = (n % BYTE_SIZE);
if (bits) {
/* Zero pad to a whole number of bytes */
unsigned r = (BYTE_SIZE - bits);
b <<= r;
n += r;
}
do {
/* Output each byte */
if (bytes >= CHUNK_SIZE) {
/* Start new chunk if necessary */
bs = extend_bitstream(bs);
text = bs->text;
bytes = 0;
}
n -= BYTE_SIZE;
text[bytes] = (character)((b >> n) & BYTE_MASK);
bytes++;
} while (n);
if (bits) {
bytes--;
}
bs->bytes = bytes;
bs->bits = bits;
}
return (bs);
}
/*
ADD A LARGER NUMBER OF BITS TO A BITSTREAM
This routine is identical to enc_bits except that it works for up to
32 bits.
*/
BITSTREAM *
enc_long_bits(BITSTREAM *bs, unsigned n, unsigned long d)
{
if (n > 16) {
bs = enc_bits(bs, n - 16,(unsigned)(d >> 16));
n = 16;
}
bs = enc_bits(bs, n,(unsigned)d);
return (bs);
}
/*
ADD A NUMBER OF BYTES TO A BITSTREAM
This routine adds the n bytes given by s to the bitstream bs.
*/
BITSTREAM *
enc_bytes(BITSTREAM *bs, unsigned long n, string s)
{
if (bs->bits) {
/* Unaligned bitstream */
unsigned long i;
for (i = 0; i < n; i++) {
unsigned c = (unsigned)s[i];
bs = enc_bits(bs,(unsigned)BYTE_SIZE, c);
}
} else {
/* Aligned bitstream */
unsigned long i;
string text = bs->text;
unsigned bytes = bs->bytes;
for (i = 0; i < n; i++) {
if (bytes >= CHUNK_SIZE) {
/* Start new chunk if necessary */
bs = extend_bitstream(bs);
text = bs->text;
bytes = 0;
}
text[bytes] = s[i];
bytes++;
}
bs->bytes = bytes;
}
return (bs);
}
/*
ADD A NUMBER OF ASCII CHARACTERS TO A BITSTREAM
This routine adds the n ASCII characters given by s to the bitstream bs.
*/
BITSTREAM *
enc_ascii(BITSTREAM *bs, unsigned long n, string s)
{
if (is_ascii) {
bs = enc_bytes(bs, n, s);
} else {
if (bs->bits) {
/* Unaligned bitstream */
unsigned long i;
for (i = 0; i < n; i++) {
int ch = CHAR_SIMPLE;
unsigned long c = (unsigned long)s[i];
c = to_ascii(c, &ch);
bs = enc_bits(bs, (unsigned)BYTE_SIZE,
(unsigned)c);
}
} else {
/* Aligned bitstream */
unsigned long i;
string text = bs->text;
unsigned bytes = bs->bytes;
for (i = 0; i < n; i++) {
int ch = CHAR_SIMPLE;
unsigned long c = (unsigned long)s[i];
if (bytes >= CHUNK_SIZE) {
/* Start new chunk if necessary */
bs = extend_bitstream(bs);
text = bs->text;
bytes = 0;
}
c = to_ascii(c, &ch);
text[bytes] = (unsigned char)c;
bytes++;
}
bs->bytes = bytes;
}
}
return (bs);
}
/*
COPY A BITSTREAM
This routine copies a component of the bitstream bs to the end of
the bitstream fs.
*/
static BITSTREAM *
copy_bitstream(BITSTREAM *fs, BITSTREAM *bs)
{
string text = bs->text;
unsigned bits = bs->bits;
unsigned bytes = bs->bytes;
if (bytes) {
/* Copy any bytes */
fs = enc_bytes(fs,(unsigned long)bytes, text);
}
if (bits) {
/* Copy any spare bits */
unsigned c = (unsigned)text[bytes];
c >>= (BYTE_SIZE - bits);
fs = enc_bits(fs, bits, c);
}
return (fs);
}
/*
JOIN TWO BITSTREAMS
This routine adds the bitstream bs to the end of the bitstream fs.
bs will not have an associated file.
*/
BITSTREAM *
join_bitstreams(BITSTREAM *fs, BITSTREAM *bs)
{
FILE *f;
BITSTREAM *ps;
if (bs == NULL) {
return (fs);
}
if (fs == NULL) {
return (bs);
}
if (fs->link == NULL) {
fs->link = bs->link;
}
/* Copy bitstream to file */
ps = bs->prev;
f = fs->file;
if (f) {
if (ps) {
fs = join_bitstreams(fs, ps);
}
if (fs->bits == 0 && bs->bytes) {
/* Dump any bytes to file */
bs->file = f;
if (fs->bytes) {
dump_bitstream(fs);
}
dump_bitstream(bs);
bs->file = NULL;
}
fs = copy_bitstream(fs, bs);
if (ps == NULL) {
end_bitstream(bs, 0);
}
return (fs);
}
/* Copy small bitstreams */
if (ps == NULL && bs->bytes < CHUNK_COPY) {
fs = copy_bitstream(fs, bs);
end_bitstream(bs, 0);
return (fs);
}
/* Link larger bitstreams */
ps = bs;
while (ps->prev) {
ps = ps->prev;
}
ps->prev = fs;
return (bs);
}
/*
FIND THE LENGTH OF A BITSTREAM
This routine returns the length of the bitstream bs in bits.
*/
unsigned
length_bitstream(BITSTREAM *bs)
{
unsigned n = 0;
while (bs) {
n += (BYTE_SIZE * bs->bytes + bs->bits);
bs = bs->prev;
}
return (n);
}
/*
ALIGN A BITSTREAM TO A BYTE BOUNDARY
This routine aligns the bitstream bs so that it consists of a whole
number of bytes.
*/
BITSTREAM *
enc_boundary(BITSTREAM *bs)
{
unsigned n = length_bitstream(bs);
unsigned r = (n % BYTE_SIZE);
if (r) {
/* Add extra bits if necessary */
bs = enc_bits(bs, BYTE_SIZE - r,(unsigned)0);
}
return (bs);
}
/*
ADD AN EXTENDED BIT PATTERN TO A BITSTREAM
This routine adds the bit pattern d to the bitstream bs using the
extended encoding as n-bit packets. Note that d cannot be zero.
*/
BITSTREAM *
enc_extn(BITSTREAM *bs, unsigned n, unsigned d)
{
unsigned e = ((unsigned)1 << n) - 1;
while (d > e) {
/* Encode zero for each multiple of e */
bs = enc_bits(bs, n,(unsigned)0);
d -= e;
}
/* Encode the remainder */
bs = enc_bits(bs, n, d);
return (bs);
}
/*
ADD A SERIES OF OCTAL DIGITS TO A BITSTREAM
This is an auxiliary routine used by enc_int. It is identical
except that the last digit is not marked.
*/
BITSTREAM *
enc_int_aux(BITSTREAM *bs, unsigned long n)
{
unsigned m;
if (n >= 8) {
bs = enc_int_aux(bs, n >> 3);
}
m = (unsigned)(n & 0x7);
bs = enc_bits(bs,(unsigned)4, m);
return (bs);
}
/*
ADD AN INTEGER TO A BITSTREAM
This routine adds the integer n as a series of octal digits to the
bitstream bs. The last digit is marked by means of a set bit.
*/
BITSTREAM *
enc_int(BITSTREAM *bs, unsigned long n)
{
unsigned m;
if (n >= 8)bs = enc_int_aux(bs, n >> 3);
m = (unsigned)((n & 0x7) | 0x8);
bs = enc_bits(bs,(unsigned)4, m);
return (bs);
}
/*
ADD AN IDENTIFIER TO A BITSTREAM
This routine adds the identifier string starting with s of length n
to the bitstream bs. This is encoded as two integers, giving the
bits per character and the number of characters, followed by an
alignment, followed by the characters comprising the identifier.
*/
BITSTREAM *
enc_ident(BITSTREAM *bs, string s, unsigned long n)
{
bs = enc_int(bs,(unsigned long)BYTE_SIZE);
bs = enc_int(bs, n);
bs = enc_boundary(bs);
bs = enc_ascii(bs, n, s);
return (bs);
}
/*
ADD A STRING TO A BITSTREAM
This routine adds the string s of length n to the bitstream bs.
*/
BITSTREAM *
enc_tdfstring(BITSTREAM *bs, unsigned long n, string s)
{
bs = enc_int(bs,(unsigned long)BYTE_SIZE);
bs = enc_int(bs, n);
bs = enc_ascii(bs, n, s);
return (bs);
}
/*
ADD A STRING TO A BITSTREAM
This routine is identical to enc_tdfstring except that strlen is
used to calculate the length of the string.
*/
BITSTREAM *
enc_ustring(BITSTREAM *bs, string s)
{
unsigned long n = (unsigned long)ustrlen(s);
bs = enc_int(bs,(unsigned long)BYTE_SIZE);
bs = enc_int(bs, n);
bs = enc_ascii(bs, n, s);
return (bs);
}
/*
ADD A TDF BITSTREAM TO A BITSTREAM
This routine adds the bitstream ps, preceded by its length, to the
bitstream bs.
*/
BITSTREAM *
enc_bitstream(BITSTREAM *bs, BITSTREAM *ps)
{
unsigned n = length_bitstream(ps);
bs = enc_int(bs,(unsigned long)n);
bs = join_bitstreams(bs, ps);
return (bs);
}