bitmath.c (3303B)
1 /* libFLAC - Free Lossless Audio Codec library 2 * Copyright (C) 2001,2002,2003,2004,2005 Josh Coalson 3 * 4 * Redistribution and use in source and binary forms, with or without 5 * modification, are permitted provided that the following conditions 6 * are met: 7 * 8 * - Redistributions of source code must retain the above copyright 9 * notice, this list of conditions and the following disclaimer. 10 * 11 * - Redistributions in binary form must reproduce the above copyright 12 * notice, this list of conditions and the following disclaimer in the 13 * documentation and/or other materials provided with the distribution. 14 * 15 * - Neither the name of the Xiph.org Foundation nor the names of its 16 * contributors may be used to endorse or promote products derived from 17 * this software without specific prior written permission. 18 * 19 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 20 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 21 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 22 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR 23 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, 24 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 25 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 26 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 27 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 28 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 29 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 30 */ 31 32 #include "private/bitmath.h" 33 #include "FLAC/assert.h" 34 35 /* An example of what FLAC__bitmath_ilog2() computes: 36 * 37 * ilog2( 0) = assertion failure 38 * ilog2( 1) = 0 39 * ilog2( 2) = 1 40 * ilog2( 3) = 1 41 * ilog2( 4) = 2 42 * ilog2( 5) = 2 43 * ilog2( 6) = 2 44 * ilog2( 7) = 2 45 * ilog2( 8) = 3 46 * ilog2( 9) = 3 47 * ilog2(10) = 3 48 * ilog2(11) = 3 49 * ilog2(12) = 3 50 * ilog2(13) = 3 51 * ilog2(14) = 3 52 * ilog2(15) = 3 53 * ilog2(16) = 4 54 * ilog2(17) = 4 55 * ilog2(18) = 4 56 */ 57 unsigned FLAC__bitmath_ilog2(FLAC__uint32 v) 58 { 59 unsigned l = 0; 60 FLAC__ASSERT(v > 0); 61 while(v >>= 1) 62 l++; 63 return l; 64 } 65 66 unsigned FLAC__bitmath_ilog2_wide(FLAC__uint64 v) 67 { 68 unsigned l = 0; 69 FLAC__ASSERT(v > 0); 70 while(v >>= 1) 71 l++; 72 return l; 73 } 74 75 /* An example of what FLAC__bitmath_silog2() computes: 76 * 77 * silog2(-10) = 5 78 * silog2(- 9) = 5 79 * silog2(- 8) = 4 80 * silog2(- 7) = 4 81 * silog2(- 6) = 4 82 * silog2(- 5) = 4 83 * silog2(- 4) = 3 84 * silog2(- 3) = 3 85 * silog2(- 2) = 2 86 * silog2(- 1) = 2 87 * silog2( 0) = 0 88 * silog2( 1) = 2 89 * silog2( 2) = 3 90 * silog2( 3) = 3 91 * silog2( 4) = 4 92 * silog2( 5) = 4 93 * silog2( 6) = 4 94 * silog2( 7) = 4 95 * silog2( 8) = 5 96 * silog2( 9) = 5 97 * silog2( 10) = 5 98 */ 99 unsigned FLAC__bitmath_silog2(int v) 100 { 101 while(1) { 102 if(v == 0) { 103 return 0; 104 } 105 else if(v > 0) { 106 unsigned l = 0; 107 while(v) { 108 l++; 109 v >>= 1; 110 } 111 return l+1; 112 } 113 else if(v == -1) { 114 return 2; 115 } 116 else { 117 v++; 118 v = -v; 119 } 120 } 121 } 122 123 unsigned FLAC__bitmath_silog2_wide(FLAC__int64 v) 124 { 125 while(1) { 126 if(v == 0) { 127 return 0; 128 } 129 else if(v > 0) { 130 unsigned l = 0; 131 while(v) { 132 l++; 133 v >>= 1; 134 } 135 return l+1; 136 } 137 else if(v == -1) { 138 return 2; 139 } 140 else { 141 v++; 142 v = -v; 143 } 144 } 145 }