1 /*
2     Scan Tailor - Interactive post-processing tool for scanned pages.
3     Copyright (C) 2007-2008  Joseph Artsimovich <joseph_a@mail.ru>
4 
5     This program is free software: you can redistribute it and/or modify
6     it under the terms of the GNU General Public License as published by
7     the Free Software Foundation, either version 3 of the License, or
8     (at your option) any later version.
9 
10     This program is distributed in the hope that it will be useful,
11     but WITHOUT ANY WARRANTY; without even the implied warranty of
12     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13     GNU General Public License for more details.
14 
15     You should have received a copy of the GNU General Public License
16     along with this program.  If not, see <http://www.gnu.org/licenses/>.
17  */
18 
19 #ifndef IMAGEPROC_BITOPS_H_
20 #define IMAGEPROC_BITOPS_H_
21 
22 namespace imageproc {
23 namespace detail {
24 extern const unsigned char bitCounts[256];
25 extern const unsigned char reversedBits[256];
26 
27 template <typename T, int BytesRemaining>
28 class NonZeroBits {
29  public:
count(T val)30   static unsigned char count(T val) {
31     return bitCounts[static_cast<unsigned char>(val)] + NonZeroBits<T, BytesRemaining - 1>::count(val >> 8);
32   }
33 };
34 
35 
36 template <typename T>
37 class NonZeroBits<T, 1> {
38  public:
count(T val)39   static unsigned char count(T val) { return bitCounts[static_cast<unsigned char>(val)]; }
40 };
41 
42 
43 template <typename T, int TotalBytes, int Offset, bool Done = false>
44 struct ReverseBytes {
resultReverseBytes45   static T result(const T val) {
46     const int left_shift = (TotalBytes - Offset - 1) * 8;
47     const int right_shift = Offset * 8;
48 
49     typedef unsigned char Byte;
50     const Byte left_byte = static_cast<Byte>(val >> left_shift);
51     const Byte right_byte = static_cast<Byte>(val >> right_shift);
52 
53     T res(ReverseBytes<T, TotalBytes, Offset + 1, Offset == TotalBytes / 2>::result(val));
54     res |= T(reversedBits[left_byte]) << right_shift;
55     res |= T(reversedBits[right_byte]) << left_shift;
56 
57     return res;
58   }
59 };
60 
61 template <typename T, int TotalBytes, int Offset>
62 struct ReverseBytes<T, TotalBytes, Offset, true> {
63   static T result(T) { return T(); }
64 };
65 
66 template <typename T>
67 struct ReverseBytes<T, 1, 0, false> {
68   static T result(const T val) {
69     typedef unsigned char Byte;
70 
71     return T(reversedBits[static_cast<Byte>(val)]);
72   }
73 };
74 
75 
76 template <typename T, int STRIPE_LEN, int BITS_DONE = 0, bool HAVE_MORE_BITS = true>
77 struct StripedMaskMSB1 {
78   static const T value
79       = (((T(1) << STRIPE_LEN) - 1) << (BITS_DONE + STRIPE_LEN))
80         | StripedMaskMSB1<T, STRIPE_LEN, BITS_DONE + STRIPE_LEN * 2, BITS_DONE + STRIPE_LEN * 2 < sizeof(T) * 8>::value;
81 };
82 
83 template <typename T, int STRIPE_LEN, int BITS_DONE>
84 struct StripedMaskMSB1<T, STRIPE_LEN, BITS_DONE, false> {
85   static const T value = 0;
86 };
87 
88 
89 template <typename T, int STRIPE_LEN, int BITS_DONE = 0, bool HAVE_MORE_BITS = true>
90 struct StripedMaskLSB1 {
91   static const T value
92       = (((T(1) << STRIPE_LEN) - 1) << BITS_DONE)
93         | StripedMaskLSB1<T, STRIPE_LEN, BITS_DONE + STRIPE_LEN * 2, BITS_DONE + STRIPE_LEN * 2 < sizeof(T) * 8>::value;
94 };
95 
96 template <typename T, int STRIPE_LEN, int BITS_DONE>
97 struct StripedMaskLSB1<T, STRIPE_LEN, BITS_DONE, false> {
98   static const T value = 0;
99 };
100 
101 
102 template <typename T, int STRIPE_LEN>
103 struct MostSignificantZeroes {
104   static int reduce(T val, int count) {
105     if (T tmp = val & StripedMaskMSB1<T, STRIPE_LEN>::value) {
106       val = tmp;
107       count -= STRIPE_LEN;
108     }
109 
110     return MostSignificantZeroes<T, STRIPE_LEN / 2>::reduce(val, count);
111   }
112 };
113 
114 template <typename T>
115 struct MostSignificantZeroes<T, 0> {
116   static int reduce(T val, int count) { return count - 1; }
117 };
118 
119 
120 template <typename T, int STRIPE_LEN>
121 struct LeastSignificantZeroes {
122   static int reduce(T val, int count) {
123     if (T tmp = val & StripedMaskLSB1<T, STRIPE_LEN>::value) {
124       val = tmp;
125       count -= STRIPE_LEN;
126     }
127 
128     return LeastSignificantZeroes<T, STRIPE_LEN / 2>::reduce(val, count);
129   }
130 };
131 
132 template <typename T>
133 struct LeastSignificantZeroes<T, 0> {
134   static int reduce(T val, int count) { return count - 1; }
135 };
136 }  // namespace detail
137 
138 template <typename T>
139 int countNonZeroBits(const T val) {
140   return detail::NonZeroBits<T, sizeof(T)>::count(val);
141 }
142 
143 template <typename T>
144 T reverseBits(const T val) {
145   return detail::ReverseBytes<T, sizeof(T), 0>::result(val);
146 }
147 
148 template <typename T>
149 int countMostSignificantZeroes(const T val) {
150   static const int total_bits = sizeof(T) * 8;
151   int zeroes = total_bits;
152 
153   if (val) {
154     zeroes = detail::MostSignificantZeroes<T, total_bits / 2>::reduce(val, zeroes);
155   }
156 
157   return zeroes;
158 }
159 
160 template <typename T>
161 int countLeastSignificantZeroes(const T val) {
162   static const int total_bits = sizeof(T) * 8;
163   int zeroes = total_bits;
164 
165   if (val) {
166     zeroes = detail::LeastSignificantZeroes<T, total_bits / 2>::reduce(val, zeroes);
167   }
168 
169   return zeroes;
170 }
171 }  // namespace imageproc
172 #endif  // ifndef IMAGEPROC_BITOPS_H_
173