P99
p99_arith.h
Go to the documentation of this file.
1 /* This may look like nonsense, but it really is -*- mode: C; coding: utf-8 -*- */
2 /* */
3 /* Except for parts copied from previous work and as explicitly stated below, */
4 /* the authors and copyright holders for this work are as follows: */
5 /* (C) copyright 2013 Jens Gustedt, INRIA, France */
6 /* (C) copyright 2013 Pierre-Nicolas Clauss */
7 /* */
8 /* This file is free software; it is part of the P99 project. */
9 /* */
10 /* Licensed under the Apache License, Version 2.0 (the "License"); */
11 /* you may not use this file except in compliance with the License. */
12 /* You may obtain a copy of the License at */
13 /* */
14 /* http://www.apache.org/licenses/LICENSE-2.0 */
15 /* */
16 /* Unless required by applicable law or agreed to in writing, software */
17 /* distributed under the License is distributed on an "AS IS" BASIS, */
18 /* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
19 /* See the License for the specific language governing permissions and */
20 /* limitations under the License. */
21 /* */
22 #ifndef P99_ARITH_H_
23 # define P99_ARITH_H_
24 
30 #include "p99_int.h"
31 
32 #define P00_UINTMAX_HIGHBIT(X) ((((uintmax_t)+(X)) & (UINTMAX_MAX ^ INTMAX_MAX)) >> (P99_UINTMAX_WIDTH - 1U))
33 
34 /* The wonders of unsigned types make it act as if it were a signed
35  number in 2complement representation. Unsigned types always have
36  logical shift so we negate the result to simulate an arithmetic
37  shift in that special case.
38 
39  To get back to intmax_t even more wonders occur. The result of
40  P99_UINTMAX_HIGHBIT is 0 or 1 and so it fits into intmax_t. That
41  converted value then can be negated to obtain 0 or -1 as a
42  result. */
43 #define P00_ARITH_INTMAX_SHIFT(X) (-((intmax_t)+P00_UINTMAX_HIGHBIT(X)))
44 
46 p99_inline uintmax_t p00_arith_abs(uintmax_t p00_a) {
47 #if UINTMAX_MAX > INTMAX_MAX
48  register uintmax_t p00_m = P00_ARITH_INTMAX_SHIFT(p00_a);
49  return (p00_m ^ p00_a) - p00_m;
50 #else
51  /* On such a perverted architecture the case of INTMAX_MIN might
52  raise a application defined signal. */
53  return (p00_a < 0) ? -p00_a : p00_a;
54 #endif
55 }
56 #define p99_arith_abs(X) (P99_SIGNED(X) ? p00_arith_abs(X) : P99_RVAL(uintmax_t, (X)))
57 
59 p99_inline intmax_t p99_arith_min(intmax_t p00_a, intmax_t p00_b) {
60 #if UINTMAX_MAX > INTMAX_MAX
61  p00_a -= p00_b;
62  return (p00_a & P00_ARITH_INTMAX_SHIFT(p00_a)) + p00_b;
63 #else
64  return p00_a < p00_b ? p00_a : p00_b;
65 #endif
66 }
67 
69 p99_inline intmax_t p99_arith_max(intmax_t p00_a, intmax_t p00_b) {
70 #if UINTMAX_MAX > INTMAX_MAX
71  p00_a -= p00_b;
72  return (p00_a & ~P00_ARITH_INTMAX_SHIFT(p00_a)) + p00_b;
73 #else
74  return p00_a < p00_b ? p00_b : p00_a;
75 #endif
76 }
77 
80  /* Any decent compiler will unroll this loop */
81  for(uintmax_t p00_s = 1; p00_s <= P99_EWIDTH(p00_a) >> 1; p00_s <<= 1) {
82  p00_a |= p00_a >> p00_s;
83  }
84  return p00_a - (p00_a >> 1);
85 }
86 
89  --p00_a;
90  /* Any decent compiler will unroll this loop */
91  for(uintmax_t p00_s = 1; p00_s <= P99_EWIDTH(p00_a) >> 1; p00_s <<= 1) {
92  p00_a |= p00_a >> p00_s;
93  }
94  return p00_a + 1;
95 }
96 
102  uintmax_t p00_l = 0;
103  /* If P99_UINTMAX_WIDTH is a power of two, things are relatively
104  simple. */
105 #if P99_LOW2(P99_UINTMAX_WIDTH) == P99_UINTMAX_WIDTH
106  P99_CONSTANT(int, p00_ll, P99_HIGH2(P99_UINTMAX_WIDTH) - 1);
107 #else
108  /* If not, we xor out the lowest bit until a power of two
109  remains. This while loop should result in a compile time
110  computation, but who knows. */
111  unsigned p00_ll = P99_UINTMAX_WIDTH;
112  while (P99_LOW2(p00_ll) != p00_ll) p00_ll ^= P99_LOW2(p00_ll);
113  p00_ll = P99_HIGH2(p00_ll) - 1;
114 #endif
115  /* Any decent compiler will unroll this loop */
116  for(int p00_i = p00_ll; p00_i >= 0; --p00_i) {
117  uintmax_t p00_s = UINTMAX_C(1) << p00_i;
118  uintmax_t p00_m = ((UINTMAX_C(1) << p00_s) - 1) << p00_s;
119  uintmax_t p00_t = !!(p00_a & p00_m);
120 
121  p00_l |= p00_t * p00_s;
122  p00_a >>= p00_t * p00_s;
123  }
124  return p00_l;
125 }
126 
127 #endif /* !P99_ARITH_H_ */
uintmax_t
uintmax_t
Definition: p99_str.h:117
p99_arith_min
P99_CONST_FUNCTION intmax_t p99_arith_min(intmax_t p00_a, intmax_t p00_b)
Definition: p99_arith.h:59
P99_CONSTANT
#define P99_CONSTANT(T, NAME, INIT)
define a compile time constant NAME of type T with value INIT
Definition: p99_enum.h:258
p99_arith_prev_pow2
P99_CONST_FUNCTION uintmax_t p99_arith_prev_pow2(uintmax_t p00_a)
Definition: p99_arith.h:79
p99_arith_max
P99_CONST_FUNCTION intmax_t p99_arith_max(intmax_t p00_a, intmax_t p00_b)
Definition: p99_arith.h:69
p99_arith_log2
P99_CONST_FUNCTION uintmax_t p99_arith_log2(uintmax_t p00_a)
Computes the floored base-2 logarithm.
Definition: p99_arith.h:101
p99_inline
#define p99_inline
Try to force a function always to be inlined.
Definition: p99_compiler.h:496
P99_LOW2
#define P99_LOW2(X)
extract the least significant bit that is non zero
Definition: p99_int.h:1246
P99_CONST_FUNCTION
#define P99_CONST_FUNCTION
On architectures that support this, assert that a function is "const", i.e only depends on parameters...
Definition: p99_compiler.h:622
P99_UINTMAX_WIDTH
#define P99_UINTMAX_WIDTH
Definition: p99_generated.h:8660
P99_HIGH2
#define P99_HIGH2(X)
Definition: p99_int.h:178
p99_arith_next_pow2
P99_CONST_FUNCTION uintmax_t p99_arith_next_pow2(uintmax_t p00_a)
Definition: p99_arith.h:88
P99_EWIDTH
#define P99_EWIDTH(EXPR)
The width of the integral type of expression EXPR.
Definition: p99_int.h:551
p99_int.h
Macros handling integer types and initialization.