1/**********
2This library is free software; you can redistribute it and/or modify it under
3the terms of the GNU Lesser General Public License as published by the
4Free Software Foundation; either version 3 of the License, or (at your
5option) any later version. (See <http://www.gnu.org/copyleft/lesser.html>.)
6
7This library is distributed in the hope that it will be useful, but WITHOUT
8ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
9FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for
10more details.
11
12You should have received a copy of the GNU Lesser General Public License
13along with this library; if not, write to the Free Software Foundation, Inc.,
1451 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
15**********/
16// "liveMedia"
17// Copyright (c) 1996-2020 Live Networks, Inc. All rights reserved.
18// Bit Vector data structure
19// Implementation
20
21#include "BitVector.hh"
22
23BitVector::BitVector(unsigned char* baseBytePtr,
24 unsigned baseBitOffset,
25 unsigned totNumBits) {
26 setup(baseBytePtr, baseBitOffset, totNumBits);
27}
28
29void BitVector::setup(unsigned char* baseBytePtr,
30 unsigned baseBitOffset,
31 unsigned totNumBits) {
32 fBaseBytePtr = baseBytePtr;
33 fBaseBitOffset = baseBitOffset;
34 fTotNumBits = totNumBits;
35 fCurBitIndex = 0;
36}
37
38static unsigned char const singleBitMask[8]
39 = {0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01};
40
41#define MAX_LENGTH 32
42
43void BitVector::putBits(unsigned from, unsigned numBits) {
44 if (numBits == 0) return;
45
46 unsigned char tmpBuf[4];
47 unsigned overflowingBits = 0;
48
49 if (numBits > MAX_LENGTH) {
50 numBits = MAX_LENGTH;
51 }
52
53 if (numBits > fTotNumBits - fCurBitIndex) {
54 overflowingBits = numBits - (fTotNumBits - fCurBitIndex);
55 }
56
57 tmpBuf[0] = (unsigned char)(from>>24);
58 tmpBuf[1] = (unsigned char)(from>>16);
59 tmpBuf[2] = (unsigned char)(from>>8);
60 tmpBuf[3] = (unsigned char)from;
61
62 shiftBits(fBaseBytePtr, fBaseBitOffset + fCurBitIndex, /* to */
63 tmpBuf, MAX_LENGTH - numBits, /* from */
64 numBits - overflowingBits /* num bits */);
65 fCurBitIndex += numBits - overflowingBits;
66}
67
68void BitVector::put1Bit(unsigned bit) {
69 // The following is equivalent to "putBits(..., 1)", except faster:
70 if (fCurBitIndex >= fTotNumBits) { /* overflow */
71 return;
72 } else {
73 unsigned totBitOffset = fBaseBitOffset + fCurBitIndex++;
74 unsigned char mask = singleBitMask[totBitOffset%8];
75 if (bit) {
76 fBaseBytePtr[totBitOffset/8] |= mask;
77 } else {
78 fBaseBytePtr[totBitOffset/8] &=~ mask;
79 }
80 }
81}
82
83unsigned BitVector::getBits(unsigned numBits) {
84 if (numBits == 0) return 0;
85
86 unsigned char tmpBuf[4];
87 unsigned overflowingBits = 0;
88
89 if (numBits > MAX_LENGTH) {
90 numBits = MAX_LENGTH;
91 }
92
93 if (numBits > fTotNumBits - fCurBitIndex) {
94 overflowingBits = numBits - (fTotNumBits - fCurBitIndex);
95 }
96
97 shiftBits(tmpBuf, 0, /* to */
98 fBaseBytePtr, fBaseBitOffset + fCurBitIndex, /* from */
99 numBits - overflowingBits /* num bits */);
100 fCurBitIndex += numBits - overflowingBits;
101
102 unsigned result
103 = (tmpBuf[0]<<24) | (tmpBuf[1]<<16) | (tmpBuf[2]<<8) | tmpBuf[3];
104 result >>= (MAX_LENGTH - numBits); // move into low-order part of word
105 result &= (0xFFFFFFFF << overflowingBits); // so any overflow bits are 0
106 return result;
107}
108
109unsigned BitVector::get1Bit() {
110 // The following is equivalent to "getBits(1)", except faster:
111
112 if (fCurBitIndex >= fTotNumBits) { /* overflow */
113 return 0;
114 } else {
115 unsigned totBitOffset = fBaseBitOffset + fCurBitIndex++;
116 unsigned char curFromByte = fBaseBytePtr[totBitOffset/8];
117 unsigned result = (curFromByte >> (7-(totBitOffset%8))) & 0x01;
118 return result;
119 }
120}
121
122void BitVector::skipBits(unsigned numBits) {
123 if (numBits > fTotNumBits - fCurBitIndex) { /* overflow */
124 fCurBitIndex = fTotNumBits;
125 } else {
126 fCurBitIndex += numBits;
127 }
128}
129
130unsigned BitVector::get_expGolomb() {
131 unsigned numLeadingZeroBits = 0;
132 unsigned codeStart = 1;
133
134 while (get1Bit() == 0 && fCurBitIndex < fTotNumBits) {
135 ++numLeadingZeroBits;
136 codeStart *= 2;
137 }
138
139 return codeStart - 1 + getBits(numLeadingZeroBits);
140}
141
142int BitVector::get_expGolombSigned() {
143 unsigned codeNum = get_expGolomb();
144
145 if ((codeNum&1) == 0) { // even
146 return -(int)(codeNum/2);
147 } else { // odd
148 return (codeNum+1)/2;
149 }
150}
151
152void shiftBits(unsigned char* toBasePtr, unsigned toBitOffset,
153 unsigned char const* fromBasePtr, unsigned fromBitOffset,
154 unsigned numBits) {
155 if (numBits == 0) return;
156
157 /* Note that from and to may overlap, if from>to */
158 unsigned char const* fromBytePtr = fromBasePtr + fromBitOffset/8;
159 unsigned fromBitRem = fromBitOffset%8;
160 unsigned char* toBytePtr = toBasePtr + toBitOffset/8;
161 unsigned toBitRem = toBitOffset%8;
162
163 while (numBits-- > 0) {
164 unsigned char fromBitMask = singleBitMask[fromBitRem];
165 unsigned char fromBit = (*fromBytePtr)&fromBitMask;
166 unsigned char toBitMask = singleBitMask[toBitRem];
167
168 if (fromBit != 0) {
169 *toBytePtr |= toBitMask;
170 } else {
171 *toBytePtr &=~ toBitMask;
172 }
173
174 if (++fromBitRem == 8) {
175 ++fromBytePtr;
176 fromBitRem = 0;
177 }
178 if (++toBitRem == 8) {
179 ++toBytePtr;
180 toBitRem = 0;
181 }
182 }
183}
184