00001 // Filename: pbitops.I 00002 // Created by: drose (10May08) 00003 // 00004 //////////////////////////////////////////////////////////////////// 00005 // 00006 // PANDA 3D SOFTWARE 00007 // Copyright (c) Carnegie Mellon University. All rights reserved. 00008 // 00009 // All use of this software is subject to the terms of the revised BSD 00010 // license. You should have received a copy of this license along 00011 // with this source code in a file named "LICENSE." 00012 // 00013 //////////////////////////////////////////////////////////////////// 00014 00015 00016 //////////////////////////////////////////////////////////////////// 00017 // Function: count_bits_in_word 00018 // Description: Returns the number of 1 bits in the indicated word. 00019 //////////////////////////////////////////////////////////////////// 00020 INLINE int 00021 count_bits_in_word(PN_uint16 x) { 00022 return (int)num_bits_on[x]; 00023 } 00024 00025 //////////////////////////////////////////////////////////////////// 00026 // Function: count_bits_in_word 00027 // Description: Returns the number of 1 bits in the indicated word. 00028 //////////////////////////////////////////////////////////////////// 00029 INLINE int 00030 count_bits_in_word(PN_uint32 x) { 00031 return (int)num_bits_on[x & 0xffff] + (int)num_bits_on[(x >> 16) & 0xffff]; 00032 } 00033 00034 //////////////////////////////////////////////////////////////////// 00035 // Function: count_bits_in_word 00036 // Description: Returns the number of 1 bits in the indicated word. 00037 //////////////////////////////////////////////////////////////////// 00038 INLINE int 00039 count_bits_in_word(PN_uint64 x) { 00040 return count_bits_in_word((PN_uint32)x) + count_bits_in_word((PN_uint32)(x >> 32)); 00041 } 00042 00043 //////////////////////////////////////////////////////////////////// 00044 // Function: flood_bits_down 00045 // Description: Returns a value such that every bit at or below the 00046 // highest bit in x is 1. 00047 //////////////////////////////////////////////////////////////////// 00048 INLINE PN_uint16 00049 flood_bits_down(PN_uint16 x) { 00050 x |= (x >> 1); 00051 x |= (x >> 2); 00052 x |= (x >> 4); 00053 x |= (x >> 8); 00054 return x; 00055 } 00056 00057 //////////////////////////////////////////////////////////////////// 00058 // Function: flood_bits_down 00059 // Description: Returns a value such that every bit at or below the 00060 // highest bit in x is 1. 00061 //////////////////////////////////////////////////////////////////// 00062 INLINE PN_uint32 00063 flood_bits_down(PN_uint32 x) { 00064 x |= (x >> 1); 00065 x |= (x >> 2); 00066 x |= (x >> 4); 00067 x |= (x >> 8); 00068 x |= (x >> 16); 00069 return x; 00070 } 00071 00072 //////////////////////////////////////////////////////////////////// 00073 // Function: flood_bits_down 00074 // Description: Returns a value such that every bit at or below the 00075 // highest bit in x is 1. 00076 //////////////////////////////////////////////////////////////////// 00077 INLINE PN_uint64 00078 flood_bits_down(PN_uint64 x) { 00079 x |= (x >> 1); 00080 x |= (x >> 2); 00081 x |= (x >> 4); 00082 x |= (x >> 8); 00083 x |= (x >> 16); 00084 x |= (x >> 32); 00085 return x; 00086 } 00087 00088 //////////////////////////////////////////////////////////////////// 00089 // Function: flood_bits_up 00090 // Description: Returns a value such that every bit at or above the 00091 // highest bit in x is 1. 00092 //////////////////////////////////////////////////////////////////// 00093 INLINE PN_uint16 00094 flood_bits_up(PN_uint16 x) { 00095 x |= (x << 1); 00096 x |= (x << 2); 00097 x |= (x << 4); 00098 x |= (x << 8); 00099 return x; 00100 } 00101 00102 //////////////////////////////////////////////////////////////////// 00103 // Function: flood_bits_up 00104 // Description: Returns a value such that every bit at or above the 00105 // highest bit in x is 1. 00106 //////////////////////////////////////////////////////////////////// 00107 INLINE PN_uint32 00108 flood_bits_up(PN_uint32 x) { 00109 x |= (x << 1); 00110 x |= (x << 2); 00111 x |= (x << 4); 00112 x |= (x << 8); 00113 x |= (x << 16); 00114 return x; 00115 } 00116 00117 //////////////////////////////////////////////////////////////////// 00118 // Function: flood_bits_up 00119 // Description: Returns a value such that every bit at or above the 00120 // highest bit in x is 1. 00121 //////////////////////////////////////////////////////////////////// 00122 INLINE PN_uint64 00123 flood_bits_up(PN_uint64 x) { 00124 x |= (x << 1); 00125 x |= (x << 2); 00126 x |= (x << 4); 00127 x |= (x << 8); 00128 x |= (x << 16); 00129 x |= (x << 32); 00130 return x; 00131 } 00132 00133 //////////////////////////////////////////////////////////////////// 00134 // Function: get_lowest_on_bit 00135 // Description: Returns the index of the lowest 1 bit in the word. 00136 // Returns -1 if there are no 1 bits. 00137 //////////////////////////////////////////////////////////////////// 00138 INLINE int 00139 get_lowest_on_bit(PN_uint16 x) { 00140 if (x == 0) { 00141 return -1; 00142 } 00143 00144 PN_uint16 w = (x & (~x + 1)); 00145 return (int)num_bits_on[w - 1]; 00146 } 00147 00148 //////////////////////////////////////////////////////////////////// 00149 // Function: get_lowest_on_bit 00150 // Description: Returns the index of the lowest 1 bit in the word. 00151 // Returns -1 if there are no 1 bits. 00152 //////////////////////////////////////////////////////////////////// 00153 INLINE int 00154 get_lowest_on_bit(PN_uint32 x) { 00155 if (x == 0) { 00156 return -1; 00157 } 00158 00159 PN_uint32 w = (x & (~x + 1)); 00160 return count_bits_in_word(w - 1); 00161 } 00162 00163 //////////////////////////////////////////////////////////////////// 00164 // Function: get_lowest_on_bit 00165 // Description: Returns the index of the lowest 1 bit in the word. 00166 // Returns -1 if there are no 1 bits. 00167 //////////////////////////////////////////////////////////////////// 00168 INLINE int 00169 get_lowest_on_bit(PN_uint64 x) { 00170 if (x == 0) { 00171 return -1; 00172 } 00173 00174 PN_uint64 w = (x & (~x + 1)); 00175 return count_bits_in_word(w - 1); 00176 } 00177 00178 //////////////////////////////////////////////////////////////////// 00179 // Function: get_highest_on_bit 00180 // Description: Returns the index of the highest 1 bit in the word. 00181 // Returns -1 if there are no 1 bits. 00182 //////////////////////////////////////////////////////////////////// 00183 INLINE int 00184 get_highest_on_bit(PN_uint16 x) { 00185 PN_uint16 w = flood_bits_down(x); 00186 return count_bits_in_word(w) - 1; 00187 } 00188 00189 //////////////////////////////////////////////////////////////////// 00190 // Function: get_highest_on_bit 00191 // Description: Returns the index of the highest 1 bit in the word. 00192 // Returns -1 if there are no 1 bits. 00193 //////////////////////////////////////////////////////////////////// 00194 INLINE int 00195 get_highest_on_bit(PN_uint32 x) { 00196 PN_uint32 w = flood_bits_down(x); 00197 return count_bits_in_word(w) - 1; 00198 } 00199 00200 //////////////////////////////////////////////////////////////////// 00201 // Function: get_highest_on_bit 00202 // Description: Returns the index of the highest 1 bit in the word. 00203 // Returns -1 if there are no 1 bits. 00204 //////////////////////////////////////////////////////////////////// 00205 INLINE int 00206 get_highest_on_bit(PN_uint64 x) { 00207 PN_uint64 w = flood_bits_down(x); 00208 return count_bits_in_word(w) - 1; 00209 } 00210 00211 //////////////////////////////////////////////////////////////////// 00212 // Function: get_next_higher_bit 00213 // Description: Returns the smallest power of 2 greater than x. 00214 // 00215 // Returns the smallest number n such that (1 << n) is 00216 // larger than x. 00217 //////////////////////////////////////////////////////////////////// 00218 INLINE int 00219 get_next_higher_bit(PN_uint16 x) { 00220 PN_uint16 w = flood_bits_down(x); 00221 return count_bits_in_word(w); 00222 } 00223 00224 //////////////////////////////////////////////////////////////////// 00225 // Function: get_next_higher_bit 00226 // Description: Returns the smallest power of 2 greater than x. 00227 // 00228 // Returns the smallest number n such that (1 << n) is 00229 // larger than x. 00230 //////////////////////////////////////////////////////////////////// 00231 INLINE int 00232 get_next_higher_bit(PN_uint32 x) { 00233 PN_uint32 w = flood_bits_down(x); 00234 return count_bits_in_word(w); 00235 } 00236 00237 //////////////////////////////////////////////////////////////////// 00238 // Function: get_next_higher_bit 00239 // Description: Returns the smallest power of 2 greater than x. 00240 // 00241 // Returns the smallest number n such that (1 << n) is 00242 // larger than x. 00243 //////////////////////////////////////////////////////////////////// 00244 INLINE int 00245 get_next_higher_bit(PN_uint64 x) { 00246 PN_uint64 w = flood_bits_down(x); 00247 return count_bits_in_word(w); 00248 }