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
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
|
/**
* Copyright © 2014 Mattias Andrée (m@maandree.se)
*
* This program is free software: you can redistribute it and/or modify
* it under the terms of the GNU Affero General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU Affero General Public License for more details.
*
* You should have received a copy of the GNU Affero General Public License
* along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
#ifndef ALGO_ALGORITHMS_BITS_ABSOLUTE_H
#define ALGO_ALGORITHMS_BITS_ABSOLUTE_H
/* NB! This will not play nice if the placeholder `T` is
* not set to a type only containing [0-9A-Za-z_] (and $
* in GNU C). Therefore, with the exception of `char`,
* `short`, `int`, `long`, `float` and `double`, you
* should only use `typedef`:ed types. */
#include <limits.h>
/* Note: This file is purely academical, your compiler should
* be able to select the fast way to compute the absolute value
* if you write `(a > 0 ? a : -a)`, in GNU C:
*
* ({
* typeof(a) a_ = a;
* a_ > 0 ? a : -a;
* })
*
* GCC also have built in functions like `__builtin_labs`
* for calculating the the absolute value of a value.
*/
/**
* Compute the absolute value of an integer.
*
* This function only works on integer types. And it
* assumes that two's complement is used, which is
* always true if you use GCC and is true for most
* (all?) high-level programming languages.
*
* `algo_make_implementation_of_abs_twos_complement(T)`
* is used to make this function available for a particular
* data type `T`. And implementation without modifiers and
* attributes will be expanded. You may add `static`,
* `inline` and `__attribute__` before calling
* `algo_make_implementation_of_abs_twos_complement(T)`.
*
* `algo_make_prototype_of_abs_twos_complement(T)`
* is the prototype counterpart of
* `algo_make_implementation_of_abs_twos_complement(T)`.
* It too is will not add any modifiers or attributes by
* default. It will neither add a semicolon at the end of
* the prototype.
*
* `algo_abs_twos_complement(T)` is used to get the version
* of the function that supports the data type `T`.
* `&(algo_abs_twos_complement(T))` gets the address of this
* function and `algo_abs_twos_complement(T)(items, n, min, max)`
* calls the function.
*
* This function is constant, if you are using GCC you
* should add `__attribute__((const))` to its prototype.
*
* @param value The value whose absolute value should be calculated.
* @return The absolute value of `value`. If `value` is its
* minimum possible value, `value` will be returned
* verbatim because of overflow.
*/
//>fun () {
T algo_abs_twos_complement__##T(T value)
{
/* Compiles to three operations. */
T mask = value >> (sizeof(T) * CHAR_BIT - 1);
return (value ^ mask) - mask;
/* Or alternatively: (value + mask) ^ mask */
}
//>} ; . ../make_fun
/**
* Compute the absolute value of an integer.
*
* This function only works on integer types. And it
* assumes that ones' complement is used, which is
* seldom true and is always false if you use GCC.
*
* `algo_make_implementation_of_abs_ones_complement(T)`
* is used to make this function available for a particular
* data type `T`. And implementation without modifiers and
* attributes will be expanded. You may add `static`,
* `inline` and `__attribute__` before calling
* `algo_make_implementation_of_abs_ones_complement(T)`.
*
* `algo_make_prototype_of_abs_ones_complement(T)`
* is the prototype counterpart of
* `algo_make_implementation_of_abs_ones_complement(T)`.
* It too is will not add any modifiers or attributes by
* default. It will neither add a semicolon at the end of
* the prototype.
*
* `algo_abs_ones_complement(T)` is used to get the version
* of the function that supports the data type `T`.
* `&(algo_abs_ones_complement(T))` gets the address of this
* function and `algo_abs_ones_complement(T)(items, n, min, max)`
* calls the function.
*
* This function is constant, if you are using GCC you
* should add `__attribute__((const))` to its prototype.
*
* @param value The value whose absolute value should be calculated.
* @return The absolute value of `value`.
*/
//>fun () {
T algo_abs_ones_complement__##T(T value)
{
/* Compiles to two operations. */
T mask = value >> (sizeof(T) * CHAR_BIT - 1);
return value ^ mask;
}
//>} ; . ../make_fun
/**
* Compute the absolute value of an integer.
*
* This function only works on integer types. And it
* assumes that sign–magnitude is used, which is
* seldom true and is always false if you use GCC.
*
* `algo_make_implementation_of_abs_sign_magnitude(T)`
* is used to make this function available for a particular
* data type `T`. And implementation without modifiers and
* attributes will be expanded. You may add `static`,
* `inline` and `__attribute__` before calling
* `algo_make_implementation_of_abs_sign_magnitude(T)`.
*
* `algo_make_prototype_of_abs_sign_magnitude(T)`
* is the prototype counterpart of
* `algo_make_implementation_of_abs_sign_magnitude(T)`.
* It too is will not add any modifiers or attributes by
* default. It will neither add a semicolon at the end of
* the prototype.
*
* `algo_abs_sign_magnitude(T)` is used to get the version
* of the function that supports the data type `T`.
* `&(algo_abs_sign_magnitude(T))` gets the address of this
* function and `algo_abs_sign_magnitude(T)(items, n, min, max)`
* calls the function.
*
* This function is constant, if you are using GCC you
* should add `__attribute__((const))` to its prototype.
*
* @param value The value whose absolute value should be calculated.
* @return The absolute value of `value`.
*/
//>fun () {
T algo_abs_sign_magnitude__##T(T value)
{
/* Compiles to one operation. */
const T magnitude = ~(1 ^ -1);
return value & magnitude;
/* Or alternatively: magnitude = ~(1 << (sizeof(T) * CHAR_BIT - 1)) */
}
//>} ; . ../make_fun
#endif
|
