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 31 int numberOfTrailingZeros32(int32_t i) { 32 int64_t i64 = i; 33 i64 = (i64 & -i64) * 0x0450FBAF; 34 uint32_t u = i64; 35 return NTZ_TABLE[(u) >> 26]; 36 } 37 38 uint64_t highestOneBit(uint64_t n) { 39 n |= (n >> 1); 40 n |= (n >> 2); 41 n |= (n >> 4); 42 n |= (n >> 8); 43 n |= (n >> 16); 44 n |= (n >> 32); 45 return n - (n >> 1); 46 } 47 48 uint64_t _powerOf2(uint64_t u) { 49 uint64_t powerOf2 = highestOneBit(u); 50 return powerOf2 ? powerOf2 : 1; 51 } 52 53 // Based on Long.numberOfTrailingZeros in Long.java 54 int numberOfTrailingZeros(uint64_t u) { 55 int32_t low = u; 56 return low !=0 ? numberOfTrailingZeros32(low) 57 : 32 + numberOfTrailingZeros32((int32_t) (u >> 32)); 58 } 59 } 60 61 namespace webm { 62 63 // Encode the id and/or size of an EBML element bytes by setting a leading length descriptor bit: 64 // 65 // 1xxxxxxx - 1-byte values 66 // 01xxxxxx xxxxxxxx - 67 // 001xxxxx xxxxxxxx xxxxxxxx - 68 // 0001xxxx xxxxxxxx xxxxxxxx xxxxxxxx - ... 69 // 00001xxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx - 70 // 000001xx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx - 71 // 0000001x xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx - 72 // 00000001 xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx - 8-byte values 73 // 74 // This function uses the least the number of bytes possible. 75 uint64_t encodeUnsigned(uint64_t u) { 76 uint64_t powerOf2 = _powerOf2(u); 77 if (u + 1 == powerOf2 << 1) 78 powerOf2 <<= 1; 79 int shiftWidth = (7 + numberOfTrailingZeros(powerOf2)) / 7 * 7; 80 long lengthDescriptor = 1 << shiftWidth; 81 return lengthDescriptor | u; 82 } 83 84 // Like above but pads the input value with leading zeros up to the specified width. The length 85 // descriptor is calculated based on width. 86 uint64_t encodeUnsigned(uint64_t u, int width) { 87 int shiftWidth = 7 * width; 88 uint64_t lengthDescriptor = 1; 89 lengthDescriptor <<= shiftWidth; 90 return lengthDescriptor | u; 91 } 92 93 // Calculate the length of an EBML coded id or size from its length descriptor. 94 int sizeOf(uint64_t u) { 95 uint64_t powerOf2 = _powerOf2(u); 96 int unsignedLength = numberOfTrailingZeros(powerOf2) / 8 + 1; 97 return unsignedLength; 98 } 99 100 // Serialize an EBML coded id or size in big-endian order. 101 int serializeCodedUnsigned(uint64_t u, uint8_t* bary) { 102 int unsignedLength = sizeOf(u); 103 for (int i = unsignedLength - 1; i >= 0; i--) { 104 bary[i] = u & 0xff; 105 u >>= 8; 106 } 107 return unsignedLength; 108 } 109 110 } 111
