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