1 /*
2 Copyright (C) 2010 Perens LLC <bruce@perens.com>
3
4 All rights reserved.
5
6 This program is free software; you can redistribute it and/or modify
7 it under the terms of the GNU Lesser General Public License version 2.1, as
8 published by the Free Software Foundation. This program is
9 distributed in the hope that it will be useful, but WITHOUT ANY
10 WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
12 License for more details.
13
14 You should have received a copy of the GNU Lesser General Public License
15 along with this program; if not, see <http://www.gnu.org/licenses/>.
16 */
17
18 #include "defines.h"
19 #include "quantise.h"
20 #include <stdio.h>
21
22 /* Compile-time constants */
23 /* Size of unsigned char in bits. Assumes 8 bits-per-char. */
24 static const unsigned int WordSize = 8;
25
26 /* Mask to pick the bit component out of bitIndex. */
27 static const unsigned int IndexMask = 0x7;
28
29 /* Used to pick the word component out of bitIndex. */
30 static const unsigned int ShiftRight = 3;
31
32 /** Pack a bit field into a bit string, encoding the field in Gray code.
33 *
34 * The output is an array of unsigned char data. The fields are efficiently
35 * packed into the bit string. The Gray coding is a naive attempt to reduce
36 * the effect of single-bit errors, we expect to do a better job as the
37 * codec develops.
38 *
39 * This code would be simpler if it just set one bit at a time in the string,
40 * but would hit the same cache line more often. I'm not sure the complexity
41 * gains us anything here.
42 *
43 * Although field is currently of int type rather than unsigned for
44 * compatibility with the rest of the code, indices are always expected to
45 * be >= 0.
46 */
47 void
pack(unsigned char * bitArray,unsigned int * bitIndex,int field,unsigned int fieldWidth)48 pack(
49 unsigned char * bitArray, /* The output bit string. */
50 unsigned int * bitIndex, /* Index into the string in BITS, not bytes.*/
51 int field, /* The bit field to be packed. */
52 unsigned int fieldWidth/* Width of the field in BITS, not bytes. */
53 )
54 {
55 pack_natural_or_gray(bitArray, bitIndex, field, fieldWidth, 1);
56 }
57
58 void
pack_natural_or_gray(unsigned char * bitArray,unsigned int * bitIndex,int field,unsigned int fieldWidth,unsigned int gray)59 pack_natural_or_gray(
60 unsigned char * bitArray, /* The output bit string. */
61 unsigned int * bitIndex, /* Index into the string in BITS, not bytes.*/
62 int field, /* The bit field to be packed. */
63 unsigned int fieldWidth,/* Width of the field in BITS, not bytes. */
64 unsigned int gray /* non-zero for gray coding */
65 )
66 {
67 if (gray) {
68 /* Convert the field to Gray code */
69 field = (field >> 1) ^ field;
70 }
71
72 do {
73 unsigned int bI = *bitIndex;
74 unsigned int bitsLeft = WordSize - (bI & IndexMask);
75 unsigned int sliceWidth =
76 bitsLeft < fieldWidth ? bitsLeft : fieldWidth;
77 unsigned int wordIndex = bI >> ShiftRight;
78
79 bitArray[wordIndex] |=
80 ((unsigned char)((field >> (fieldWidth - sliceWidth))
81 << (bitsLeft - sliceWidth)));
82
83 *bitIndex = bI + sliceWidth;
84 fieldWidth -= sliceWidth;
85 } while ( fieldWidth != 0 );
86 }
87
88 /** Unpack a field from a bit string, converting from Gray code to binary.
89 *
90 */
91 int
unpack(const unsigned char * bitArray,unsigned int * bitIndex,unsigned int fieldWidth)92 unpack(
93 const unsigned char * bitArray, /* The input bit string. */
94 unsigned int * bitIndex, /* Index into the string in BITS, not bytes.*/
95 unsigned int fieldWidth/* Width of the field in BITS, not bytes. */
96 )
97 {
98 return unpack_natural_or_gray(bitArray, bitIndex, fieldWidth, 1);
99 }
100
101 /** Unpack a field from a bit string, to binary, optionally using
102 * natural or Gray code.
103 *
104 */
105 int
unpack_natural_or_gray(const unsigned char * bitArray,unsigned int * bitIndex,unsigned int fieldWidth,unsigned int gray)106 unpack_natural_or_gray(
107 const unsigned char * bitArray, /* The input bit string. */
108 unsigned int * bitIndex, /* Index into the string in BITS, not bytes.*/
109 unsigned int fieldWidth,/* Width of the field in BITS, not bytes. */
110 unsigned int gray /* non-zero for Gray coding */
111 )
112 {
113 unsigned int field = 0;
114 unsigned int t;
115
116 do {
117 unsigned int bI = *bitIndex;
118 unsigned int bitsLeft = WordSize - (bI & IndexMask);
119 unsigned int sliceWidth =
120 bitsLeft < fieldWidth ? bitsLeft : fieldWidth;
121
122 field |= (((bitArray[bI >> ShiftRight] >> (bitsLeft - sliceWidth)) & ((1 << sliceWidth) - 1)) << (fieldWidth - sliceWidth));
123
124 *bitIndex = bI + sliceWidth;
125 fieldWidth -= sliceWidth;
126 } while ( fieldWidth != 0 );
127
128 if (gray) {
129 /* Convert from Gray code to binary. Works for maximum 8-bit fields. */
130 t = field ^ (field >> 8);
131 t ^= (t >> 4);
132 t ^= (t >> 2);
133 t ^= (t >> 1);
134 }
135 else {
136 t = field;
137 }
138
139 return t;
140 }
141