NVBIO
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
popcount.h
Go to the documentation of this file.
1 /*
2  * nvbio
3  * Copyright (c) 2011-2014, NVIDIA CORPORATION. All rights reserved.
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions are met:
7  * * Redistributions of source code must retain the above copyright
8  * notice, this list of conditions and the following disclaimer.
9  * * Redistributions in binary form must reproduce the above copyright
10  * notice, this list of conditions and the following disclaimer in the
11  * documentation and/or other materials provided with the distribution.
12  * * Neither the name of the NVIDIA CORPORATION nor the
13  * names of its contributors may be used to endorse or promote products
14  * derived from this software without specific prior written permission.
15  *
16  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
17  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
18  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
19  * DISCLAIMED. IN NO EVENT SHALL NVIDIA CORPORATION BE LIABLE FOR ANY
20  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
21  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
22  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
23  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
24  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
25  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26  */
27 
28 #pragma once
29 
30 #include <nvbio/basic/types.h>
31 
32 namespace nvbio {
33 
36 
39 
43 
47 
51 
55 
59 
63 
67 
68 
72 
73 
77 
86 template <typename CountTable>
88  const uint32 b,
89  const CountTable count_table);
90 
95 
100 
103 template <uint32 N>
105 
109 template <uint32 N>
111 
115 template <uint32 N>
117 
126 template <typename CountTable>
128  const uint32 mask,
129  const CountTable count_table,
130  const uint32 i);
131 
132 // generate table for counting 11,10,01,00(pattern) for 8 bits number
133 // table [no# ] = representation ( # of count-pattern, . , . , . )
134 // ---------------------------------------------------------------------------
135 // e.g cnt_table[11111111] = 0x04000000 ( 4-11, 0-10, 0-01, 0-00 )
136 // cnt_table[00100001] = 0x00010102 ( 0-11, 1-10, 1-01, 2-00 )
137 // cnt_table[00000001] = 0x00000103 ( 0-11, 0-10, 1-01, 3-00 )
138 inline void gen_2bit_count_table(uint32* count_table)
139 {
140  for (int i = 0; i != 256; ++i)
141  {
142  uint32 x = 0;
143  for (int j = 0; j != 4; ++j)
144  x |= (((i&3) == j) + ((i>>2&3) == j) + ((i>>4&3) == j) + (i>>6 == j)) << (j<<3);
145 
146  count_table[i] = x;
147  }
148 }
149 
152 
153 } // namespace nvbio
154