1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
/*++
Copyright (c) 2012 Microsoft Corporation
Module Name:
bit_util.h
Abstract:
Bit hacking utilities.
Author:
Leonardo de Moura (leonardo) 2012-09-11.
Revision History:
--*/
#pragma once
/**
\brief Return the position of the most significant (set) bit of a
nonzero unsigned integer.
*/
unsigned msb_pos(unsigned v);
/**
\brief Return the number of leading zeros bits in a nonzero unsigned integer.
*/
unsigned nlz_core(unsigned x);
/**
\brief Return the number of leading zero bits in data (a number of sz words).
*/
unsigned nlz(unsigned sz, unsigned const * data);
/**
\brief Return the number of trailing zeros in a nonzero unsigned number.
*/
unsigned ntz_core(unsigned x);
/**
\brief Return the number of trailing zero bits in data (a number of sz words).
*/
unsigned ntz(unsigned sz, unsigned const * data);
/**
\brief dst <- src
Truncate if src_sz > dst_sz.
Fill range [src_sz, dst_sz) of dst with zeros if dst_sz > src_sz.
*/
void copy(unsigned src_sz, unsigned const * src, unsigned dst_sz, unsigned * dst);
/**
\brief Return true if all words of data are zero.
*/
bool is_zero(unsigned sz, unsigned const * data);
/**
\brief Set all words of data to zero.
*/
void reset(unsigned sz, unsigned * data);
/**
\brief dst <- src << k
Store in dst the result of shifting src k bits to the left.
The result is truncated by dst_sz.
\pre src_sz != 0
\pre dst_sz != 0
*/
void shl(unsigned src_sz, unsigned const * src, unsigned k, unsigned dst_sz, unsigned * dst);
/**
\brief dst <- src >> k
Store in dst the result of shifting src k bits to the right.
\pre dst must have size sz.
\pre src_sz != 0
\pre dst_sz != 0
*/
void shr(unsigned sz, unsigned const * src, unsigned k, unsigned * dst);
/**
\brief dst <- src >> k
Store in dst the result of shifting src k bits to the right.
Truncate if src_sz > dst_sz.
Fill range [src_sz, dst_sz) of dst with zeros if dst_sz > src_sz.
\pre src_sz != 0
\pre dst_sz != 0
*/
void shr(unsigned src_sz, unsigned const * src, unsigned k, unsigned dst_sz, unsigned * dst);
/**
\brief Return true if one of the first k bits of src is not zero.
*/
bool has_one_at_first_k_bits(unsigned sz, unsigned const * data, unsigned k);
/**
\brief data <- data + 1
Return true if no overflow occurred.
*/
bool inc(unsigned sz, unsigned * data);
/**
\brief data <- data - 1
Return true if no underflow occurred.
*/
bool dec(unsigned sz, unsigned * data);
/**
\brief Return true if data1 < data2.
Both must have the same size.
*/
bool lt(unsigned sz, unsigned * data1, unsigned * data2);
/**
\brief Store in c the a+b. This procedure assumes that a,b,c are vectors of size sz.
Return false if a+b overflows.
*/
bool add(unsigned sz, unsigned const * a, unsigned const * b, unsigned * c);