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 19namespace { 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. 24int 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 31int 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 38uint64_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 48uint64_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 54int 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 61namespace 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. 75uint64_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. 86uint64_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. 94int 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. 101int 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