1 /*
2 * Copyright (C) 2014 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 #include <stdint.h>
18
19 namespace {
20
21 // Table for Seal's algorithm for Number of Trailing Zeros. Hacker's Delight
22 // online, Figure 5-18 (http://www.hackersdelight.org/revisions.pdf)
23 // The entries whose value is -1 are never referenced.
24 int NTZ_TABLE[] = {
25 32, 0, 1, 12, 2, 6, -1, 13, 3, -1, 7, -1, -1, -1, -1, 14,
26 10, 4, -1, -1, 8, -1, -1, 25, -1, -1, -1, -1, -1, 21, 27, 15,
27 31, 11, 5, -1, -1, -1, -1, -1, 9, -1, -1, 24, -1, -1, 20, 26,
28 30, -1, -1, -1, -1, 23, -1, 19, 29, -1, 22, 18, 28, 17, 16, -1
29 };
30
numberOfTrailingZeros32(int32_t i)31 int numberOfTrailingZeros32(int32_t i) {
32 uint32_t u = (i & -i) * 0x0450FBAF;
33 return NTZ_TABLE[(u) >> 26];
34 }
35
highestOneBit(uint64_t n)36 uint64_t highestOneBit(uint64_t n) {
37 n |= (n >> 1);
38 n |= (n >> 2);
39 n |= (n >> 4);
40 n |= (n >> 8);
41 n |= (n >> 16);
42 n |= (n >> 32);
43 return n - (n >> 1);
44 }
45
_powerOf2(uint64_t u)46 uint64_t _powerOf2(uint64_t u) {
47 uint64_t powerOf2 = highestOneBit(u);
48 return powerOf2 ? powerOf2 : 1;
49 }
50
51 // Based on Long.numberOfTrailingZeros in Long.java
numberOfTrailingZeros(uint64_t u)52 int numberOfTrailingZeros(uint64_t u) {
53 int32_t low = u;
54 return low !=0 ? numberOfTrailingZeros32(low)
55 : 32 + numberOfTrailingZeros32((int32_t) (u >> 32));
56 }
57 }
58
59 namespace webm {
60
61 // Encode the id and/or size of an EBML element bytes by setting a leading length descriptor bit:
62 //
63 // 1xxxxxxx - 1-byte values
64 // 01xxxxxx xxxxxxxx -
65 // 001xxxxx xxxxxxxx xxxxxxxx -
66 // 0001xxxx xxxxxxxx xxxxxxxx xxxxxxxx - ...
67 // 00001xxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx -
68 // 000001xx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx -
69 // 0000001x xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx -
70 // 00000001 xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx - 8-byte values
71 //
72 // This function uses the least the number of bytes possible.
encodeUnsigned(uint64_t u)73 uint64_t encodeUnsigned(uint64_t u) {
74 uint64_t powerOf2 = _powerOf2(u);
75 if (u + 1 == powerOf2 << 1)
76 powerOf2 <<= 1;
77 int shiftWidth = (7 + numberOfTrailingZeros(powerOf2)) / 7 * 7;
78 long lengthDescriptor = 1 << shiftWidth;
79 return lengthDescriptor | u;
80 }
81
82 // Like above but pads the input value with leading zeros up to the specified width. The length
83 // descriptor is calculated based on width.
encodeUnsigned(uint64_t u,int width)84 uint64_t encodeUnsigned(uint64_t u, int width) {
85 int shiftWidth = 7 * width;
86 uint64_t lengthDescriptor = 1;
87 lengthDescriptor <<= shiftWidth;
88 return lengthDescriptor | u;
89 }
90
91 // Calculate the length of an EBML coded id or size from its length descriptor.
sizeOf(uint64_t u)92 int sizeOf(uint64_t u) {
93 uint64_t powerOf2 = _powerOf2(u);
94 int unsignedLength = numberOfTrailingZeros(powerOf2) / 8 + 1;
95 return unsignedLength;
96 }
97
98 // Serialize an EBML coded id or size in big-endian order.
serializeCodedUnsigned(uint64_t u,uint8_t * bary)99 int serializeCodedUnsigned(uint64_t u, uint8_t* bary) {
100 int unsignedLength = sizeOf(u);
101 for (int i = unsignedLength - 1; i >= 0; i--) {
102 bary[i] = u & 0xff;
103 u >>= 8;
104 }
105 return unsignedLength;
106 }
107
108 }
109