[Krafton Jungle] PintOS 2.0.0
크래프톤 정글 PintOS
 
Loading...
Searching...
No Matches
arithmetic.c File Reference
#include <stdint.h>
Include dependency graph for arithmetic.c:

Functions

static uint32_t divl (uint64_t n, uint32_t d)
 
static int nlz (uint32_t x)
 
static uint64_t udiv64 (uint64_t n, uint64_t d)
 
static uint32_t umod64 (uint64_t n, uint64_t d)
 
static int64_t sdiv64 (int64_t n, int64_t d)
 
static int32_t smod64 (int64_t n, int64_t d)
 
long long __divdi3 (long long n, long long d)
 
long long __moddi3 (long long n, long long d)
 
unsigned long long __udivdi3 (unsigned long long n, unsigned long long d)
 
unsigned long long __umoddi3 (unsigned long long n, unsigned long long d)
 

Function Documentation

◆ __divdi3()

long long __divdi3 ( long long  n,
long long  d 
)
151 {
152 return sdiv64 (n, d);
153}
static int64_t sdiv64(int64_t n, int64_t d)
Definition: arithmetic.c:128
Here is the call graph for this function:

◆ __moddi3()

long long __moddi3 ( long long  n,
long long  d 
)
157 {
158 return smod64 (n, d);
159}
static int32_t smod64(int64_t n, int64_t d)
Definition: arithmetic.c:138
Here is the call graph for this function:

◆ __udivdi3()

unsigned long long __udivdi3 ( unsigned long long  n,
unsigned long long  d 
)
163 {
164 return udiv64 (n, d);
165}
static uint64_t udiv64(uint64_t n, uint64_t d)
Definition: arithmetic.c:72
Here is the call graph for this function:

◆ __umoddi3()

unsigned long long __umoddi3 ( unsigned long long  n,
unsigned long long  d 
)
169 {
170 return umod64 (n, d);
171}
static uint32_t umod64(uint64_t n, uint64_t d)
Definition: arithmetic.c:121
Here is the call graph for this function:

◆ divl()

static uint32_t divl ( uint64_t  n,
uint32_t  d 
)
inlinestatic
26 {
27 uint32_t n1 = n >> 32;
28 uint32_t n0 = n;
29 uint32_t q, r;
30
31 asm ("divl %4"
32 : "=d" (r), "=a" (q)
33 : "0" (n1), "1" (n0), "rm" (d));
34
35 return q;
36}
unsigned int uint32_t
Definition: stdint.h:26
Here is the caller graph for this function:

◆ nlz()

static int nlz ( uint32_t  x)
static
41 {
42 /* This technique is portable, but there are better ways to do
43 it on particular systems. With sufficiently new enough GCC,
44 you can use __builtin_clz() to take advantage of GCC's
45 knowledge of how to do it. Or you can use the x86 BSR
46 instruction directly. */
47 int n = 0;
48 if (x <= 0x0000FFFF) {
49 n += 16;
50 x <<= 16;
51 }
52 if (x <= 0x00FFFFFF) {
53 n += 8;
54 x <<= 8;
55 }
56 if (x <= 0x0FFFFFFF) {
57 n += 4;
58 x <<= 4;
59 }
60 if (x <= 0x3FFFFFFF) {
61 n += 2;
62 x <<= 2;
63 }
64 if (x <= 0x7FFFFFFF)
65 n++;
66 return n;
67}
Here is the caller graph for this function:

◆ sdiv64()

static int64_t sdiv64 ( int64_t  n,
int64_t  d 
)
static
128 {
129 uint64_t n_abs = n >= 0 ? (uint64_t) n : -(uint64_t) n;
130 uint64_t d_abs = d >= 0 ? (uint64_t) d : -(uint64_t) d;
131 uint64_t q_abs = udiv64 (n_abs, d_abs);
132 return (n < 0) == (d < 0) ? (int64_t) q_abs : -(int64_t) q_abs;
133}
signed long long int int64_t
Definition: stdint.h:16
unsigned long long int uint64_t
Definition: stdint.h:29
Here is the call graph for this function:
Here is the caller graph for this function:

◆ smod64()

static int32_t smod64 ( int64_t  n,
int64_t  d 
)
static
138 {
139 return n - d * sdiv64 (n, d);
140}
Here is the call graph for this function:
Here is the caller graph for this function:

◆ udiv64()

static uint64_t udiv64 ( uint64_t  n,
uint64_t  d 
)
static
72 {
73 if ((d >> 32) == 0) {
74 /* Proof of correctness:
75
76 Let n, d, b, n1, and n0 be defined as in this function.
77 Let [x] be the "floor" of x. Let T = b[n1/d]. Assume d
78 nonzero. Then:
79 [n/d] = [n/d] - T + T
80 = [n/d - T] + T by (1) below
81 = [(b*n1 + n0)/d - T] + T by definition of n
82 = [(b*n1 + n0)/d - dT/d] + T
83 = [(b(n1 - d[n1/d]) + n0)/d] + T
84 = [(b[n1 % d] + n0)/d] + T, by definition of %
85 which is the expression calculated below.
86
87 (1) Note that for any real x, integer i: [x] + i = [x + i].
88
89 To prevent divl() from trapping, [(b[n1 % d] + n0)/d] must
90 be less than b. Assume that [n1 % d] and n0 take their
91 respective maximum values of d - 1 and b - 1:
92 [(b(d - 1) + (b - 1))/d] < b
93 <=> [(bd - 1)/d] < b
94 <=> [b - 1/d] < b
95 which is a tautology.
96
97 Therefore, this code is correct and will not trap. */
98 uint64_t b = 1ULL << 32;
99 uint32_t n1 = n >> 32;
100 uint32_t n0 = n;
101 uint32_t d0 = d;
102
103 return divl (b * (n1 % d0) + n0, d0) + b * (n1 / d0);
104 } else {
105 /* Based on the algorithm and proof available from
106 * http://www.hackersdelight.org/revisions.pdf. */
107 if (n < d)
108 return 0;
109 else {
110 uint32_t d1 = d >> 32;
111 int s = nlz (d1);
112 uint64_t q = divl (n >> 1, (d << s) >> 32) >> (31 - s);
113 return n - (q - 1) * d < d ? q - 1 : q;
114 }
115 }
116}
static uint32_t divl(uint64_t n, uint32_t d)
Definition: arithmetic.c:26
static int nlz(uint32_t x)
Definition: arithmetic.c:41
static uint8_t s[256]
Definition: random.c:17
Here is the call graph for this function:
Here is the caller graph for this function:

◆ umod64()

static uint32_t umod64 ( uint64_t  n,
uint64_t  d 
)
static
121 {
122 return n - d * udiv64 (n, d);
123}
Here is the call graph for this function:
Here is the caller graph for this function: