1 /* -*- mode: C++; c-basic-offset: 4; indent-tabs-mode: nil -*- */
2 // vim: ft=cpp:expandtab:ts=8:sw=4:softtabstop=4:
3 #ident "$Id$"
4 /*======
5 This file is part of TokuDB
6 
7 
8 Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved.
9 
10     TokuDBis is free software: you can redistribute it and/or modify
11     it under the terms of the GNU General Public License, version 2,
12     as published by the Free Software Foundation.
13 
14     TokuDB is distributed in the hope that it will be useful,
15     but WITHOUT ANY WARRANTY; without even the implied warranty of
16     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
17     GNU General Public License for more details.
18 
19     You should have received a copy of the GNU General Public License
20     along with TokuDB.  If not, see <http://www.gnu.org/licenses/>.
21 
22 ======= */
23 
24 #ident "Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved."
25 
26 #if !defined(_TOKUDB_MATH_H)
27 #define _TOKUDB_MATH_H
28 
29 namespace tokudb {
30 
31 // Add and subtract ints with overflow detection.
32 // Overflow detection adapted from "Hackers Delight", Henry S. Warren
33 
34 // Return a bit mask for bits 0 .. length_bits-1
35 TOKUDB_UNUSED(static uint64_t uint_mask(uint length_bits));
36 static uint64_t uint_mask(uint length_bits) {
37     return length_bits == 64 ? ~0ULL : (1ULL<<length_bits)-1;
38 }
39 
40 // Return the highest unsigned int with a given number of bits
41 TOKUDB_UNUSED(static uint64_t uint_high_endpoint(uint length_bits));
42 static uint64_t uint_high_endpoint(uint length_bits) {
43     return uint_mask(length_bits);
44 }
45 
46 // Return the lowest unsigned int with a given number of bits
47 TOKUDB_UNUSED(static uint64_t uint_low_endpoint(uint length_bits));
48 static uint64_t uint_low_endpoint(TOKUDB_UNUSED(uint length_bits)) {
49     return 0;
50 }
51 
52 // Add two unsigned integers with max maximum value.
53 // If there is an overflow then set the sum to the max.
54 // Return the sum and the overflow.
55 TOKUDB_UNUSED(static uint64_t uint_add(
56     uint64_t x,
57     uint64_t y,
58     uint length_bits,
59     bool* over));
60 static uint64_t uint_add(uint64_t x, uint64_t y, uint length_bits, bool *over) {
61     uint64_t mask = uint_mask(length_bits);
62     assert_always((x & ~mask) == 0);
63     assert_always((y & ~mask) == 0);
64     uint64_t s = (x + y) & mask;
65     *over = s < x;     // check for overflow
66     return s;
67 }
68 
69 // Subtract two unsigned ints with max maximum value.
70 // If there is an over then set the difference to 0.
71 // Return the difference and the overflow.
72 TOKUDB_UNUSED(static uint64_t uint_sub(
73     uint64_t x,
74     uint64_t y,
75     uint length_bits,
76     bool* over));
77 static uint64_t uint_sub(uint64_t x, uint64_t y, uint length_bits, bool *over) {
78     uint64_t mask = uint_mask(length_bits);
79     assert_always((x & ~mask) == 0);
80     assert_always((y & ~mask) == 0);
81     uint64_t s = (x - y) & mask;
82     *over = s > x;    // check for overflow
83     return s;
84 }
85 
86 // Return the highest int with a given number of bits
87 TOKUDB_UNUSED(static int64_t int_high_endpoint(uint length_bits));
88 static int64_t int_high_endpoint(uint length_bits) {
89     return (1ULL<<(length_bits-1))-1;
90 }
91 
92 // Return the lowest int with a given number of bits
93 TOKUDB_UNUSED(static int64_t int_low_endpoint(uint length_bits));
94 static int64_t int_low_endpoint(uint length_bits) {
95     int64_t mask = uint_mask(length_bits);
96     return (1ULL<<(length_bits-1)) | ~mask;
97 }
98 
99 // Sign extend to 64 bits an int with a given number of bits
100 TOKUDB_UNUSED(static int64_t int_sign_extend(int64_t n, uint length_bits));
101 static int64_t int_sign_extend(int64_t n, uint length_bits) {
102     if (n & (1ULL<<(length_bits-1)))
103         n |= ~uint_mask(length_bits);
104     return n;
105 }
106 
107 // Add two signed ints with max maximum value.
108 // If there is an overflow then set the sum to the max or the min of the int range,
109 // depending on the sign bit.
110 // Sign extend to 64 bits.
111 // Return the sum and the overflow.
112 TOKUDB_UNUSED(static int64_t int_add(
113     int64_t x,
114     int64_t y,
115     uint length_bits,
116     bool* over));
117 static int64_t int_add(int64_t x, int64_t y, uint length_bits, bool *over) {
118     int64_t mask = uint_mask(length_bits);
119     int64_t n = (x + y) & mask;
120     *over = (((n ^ x) & (n ^ y)) >> (length_bits-1)) & 1;    // check for overflow
121     if (n & (1LL<<(length_bits-1)))
122         n |= ~mask;    // sign extend
123     return n;
124 }
125 
126 // Subtract two signed ints.
127 // If there is an overflow then set the sum to the max or the min of the int range,
128 // depending on the sign bit.
129 // Sign extend to 64 bits.
130 // Return the sum and the overflow.
131 TOKUDB_UNUSED(static int64_t int_sub(
132     int64_t x,
133     int64_t y,
134     uint length_bits,
135     bool* over));
136 static int64_t int_sub(int64_t x, int64_t y, uint length_bits, bool *over) {
137     int64_t mask = uint_mask(length_bits);
138     int64_t n = (x - y) & mask;
139     *over = (((x ^ y) & (n ^ x)) >> (length_bits-1)) & 1;    // check for overflow
140     if (n & (1LL<<(length_bits-1)))
141         n |= ~mask;    // sign extend
142     return n;
143 }
144 
145 } // namespace tokudb
146 
147 #endif
148