michael@0: /*  GRAPHITE2 LICENSING
michael@0: 
michael@0:     Copyright 2012, SIL International
michael@0:     All rights reserved.
michael@0: 
michael@0:     This library is free software; you can redistribute it and/or modify
michael@0:     it under the terms of the GNU Lesser General Public License as published
michael@0:     by the Free Software Foundation; either version 2.1 of License, or
michael@0:     (at your option) any later version.
michael@0: 
michael@0:     This program is distributed in the hope that it will be useful,
michael@0:     but WITHOUT ANY WARRANTY; without even the implied warranty of
michael@0:     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
michael@0:     Lesser General Public License for more details.
michael@0: 
michael@0:     You should also have received a copy of the GNU Lesser General Public
michael@0:     License along with this library in the file named "LICENSE".
michael@0:     If not, write to the Free Software Foundation, 51 Franklin Street,
michael@0:     Suite 500, Boston, MA 02110-1335, USA or visit their web page on the
michael@0:     internet at http://www.fsf.org/licenses/lgpl.html.
michael@0: 
michael@0: Alternatively, the contents of this file may be used under the terms of the
michael@0: Mozilla Public License (http://mozilla.org/MPL) or the GNU General Public
michael@0: License, as published by the Free Software Foundation, either version 2
michael@0: of the License or (at your option) any later version.
michael@0: */
michael@0: #pragma once
michael@0: 
michael@0: namespace graphite2
michael@0: {
michael@0: 
michael@0: template<typename T>
michael@0: inline unsigned int bit_set_count(T v)
michael@0: {
michael@0:     v = v - ((v >> 1) & T(~T(0)/3));                           // temp
michael@0:     v = (v & T(~T(0)/15*3)) + ((v >> 2) & T(~T(0)/15*3));      // temp
michael@0:     v = (v + (v >> 4)) & T(~T(0)/255*15);                      // temp
michael@0:     return (T)(v * T(~T(0)/255)) >> (sizeof(T)-1)*8;           // count
michael@0: }
michael@0: 
michael@0: 
michael@0: template<int S>
michael@0: inline unsigned long _mask_over_val(unsigned long v)
michael@0: {
michael@0:     v = _mask_over_val<S/2>(v);
michael@0:     v |= v >> S*4;
michael@0:     return v;
michael@0: }
michael@0: 
michael@0: template<>
michael@0: inline unsigned long _mask_over_val<1>(unsigned long v)
michael@0: {
michael@0:     v |= v >> 1;
michael@0:     v |= v >> 2;
michael@0:     v |= v >> 4;
michael@0:     return v;
michael@0: }
michael@0: 
michael@0: template<typename T>
michael@0: inline T mask_over_val(T v)
michael@0: {
michael@0:     return _mask_over_val<sizeof(T)>(v);
michael@0: }
michael@0: 
michael@0: template<typename T>
michael@0: inline unsigned long next_highest_power2(T v)
michael@0: {
michael@0:     return _mask_over_val<sizeof(T)>(v-1)+1;
michael@0: }
michael@0: 
michael@0: template<typename T>
michael@0: inline unsigned int log_binary(T v)
michael@0: {
michael@0:     return bit_set_count(mask_over_val(v))-1;
michael@0: }
michael@0: 
michael@0: template<typename T>
michael@0: inline T has_zero(const T x)
michael@0: {
michael@0:     return (x - T(~T(0)/255)) & ~x & T(~T(0)/255*128);
michael@0: }
michael@0: 
michael@0: template<typename T>
michael@0: inline T zero_bytes(const T x, unsigned char n)
michael@0: {
michael@0:     const T t = T(~T(0)/255*n);
michael@0:     return T((has_zero(x^t) >> 7)*n);
michael@0: }
michael@0: 
michael@0: }