1/*
2 * bits.h
3 *
4 * Copyright (C) 2018 Aerospike, Inc.
5 *
6 * Portions may be licensed to Aerospike, Inc. under one or more contributor
7 * license agreements.
8 *
9 * This program is free software: you can redistribute it and/or modify it under
10 * the terms of the GNU Affero General Public License as published by the Free
11 * Software Foundation, either version 3 of the License, or (at your option) any
12 * later version.
13 *
14 * This program is distributed in the hope that it will be useful, but WITHOUT
15 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
16 * FOR A PARTICULAR PURPOSE. See the GNU Affero General Public License for more
17 * details.
18 *
19 * You should have received a copy of the GNU Affero General Public License
20 * along with this program. If not, see http://www.gnu.org/licenses/
21 */
22
23#pragma once
24
25//==========================================================
26// Includes.
27//
28
29#include <stdint.h>
30
31
32//==========================================================
33// Public API.
34//
35
36// Position of most significant bit, 0 ... 63 from low to high. -1 for value 0.
37static inline int
38cf_msb(uint64_t value)
39{
40 int n = -1;
41
42 while (value != 0) {
43 value >>= 1;
44 n++;
45 }
46
47 return n;
48}
49
50// Returns number of trailing zeros in a uint64_t, 64 for x == 0.
51static inline uint32_t
52cf_lsb64(uint64_t x)
53{
54 if (x == 0) {
55 return 64;
56 }
57
58 return (uint32_t)__builtin_ctzll(x);
59}
60
61// Returns number of leading zeros in a uint64_t, 64 for x == 0.
62static inline uint32_t
63cf_msb64(uint64_t x)
64{
65 if (x == 0) {
66 return 64;
67 }
68
69 return (uint32_t)__builtin_clzll(x);
70}
71
72static inline uint32_t
73cf_bit_count64(uint64_t x)
74{
75 x -= (x >> 1) & 0x5555555555555555;
76 x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333);
77 x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f;
78
79 return (uint32_t)((x * 0x0101010101010101) >> 56);
80}
81
82// Number of bytes occupied by val converted to a "uintvar".
83static inline uint32_t
84uintvar_size(uint32_t val)
85{
86 if ((val & 0xFFFFff80) == 0) {
87 return 1;
88 }
89
90 if ((val & 0xFFFFc000) == 0) {
91 return 2;
92 }
93
94 if ((val & 0xFFE00000) == 0) {
95 return 3;
96 }
97
98 if ((val & 0xF0000000) == 0) {
99 return 4;
100 }
101
102 return 5;
103}
104
105static inline uint8_t *
106uintvar_pack(uint8_t *buf, uint32_t val)
107{
108 if ((val & 0xFFFFff80) == 0) { // one byte only - most common
109 *buf++ = (uint8_t)val;
110 return buf;
111 }
112
113 if ((val & 0xFFFFc000) == 0) { // two bytes - next most common
114 *buf++ = (uint8_t)(val >> 7) | 0x80;
115 *buf++ = (uint8_t)(val & 0x7F);
116 return buf;
117 }
118
119 // More explicit cases have odd performance testing results, so just loop
120 // for everything that would take more than two bytes...
121
122 for (int i = 4; i > 0; i--) {
123 uint32_t shift_val = val >> (7 * i);
124
125 if (shift_val != 0) {
126 *buf++ = (uint8_t)(shift_val | 0x80);
127 }
128 }
129
130 *buf++ = (uint8_t)(val & 0x7F);
131
132 return buf;
133}
134
135static inline uint32_t
136uintvar_parse(const uint8_t** pp_read, const uint8_t* end)
137{
138 const uint8_t* p_read = *pp_read;
139
140 if (p_read >= end) {
141 *pp_read = NULL;
142 return 0;
143 }
144
145 if ((*p_read & 0x80) == 0) { // one byte only - most common - done
146 *pp_read = p_read + 1;
147 return *p_read;
148 }
149
150 if (*p_read == 0x80) { // leading zeros are illegal
151 *pp_read = NULL;
152 return 0;
153 }
154
155 uint32_t val = 0;
156
157 do {
158 val |= *p_read++ & 0x7F;
159 val <<= 7;
160
161 if (p_read >= end) {
162 break;
163 }
164
165 if ((*p_read & 0x80) == 0) { // no continuation bit - last byte - done
166 val |= *p_read;
167 *pp_read = p_read + 1;
168 return val;
169 }
170 } while ((val & 0xFE000000) == 0); // don't shift significant bits off top
171
172 *pp_read = NULL;
173
174 return 0;
175}
176