-
Notifications
You must be signed in to change notification settings - Fork 5.3k
/
pm_number.c
164 lines (149 loc) · 4.82 KB
/
pm_number.c
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
#include "prism/util/pm_number.h"
/**
* Create a new node for a number in the linked list.
*/
static pm_number_node_t *
pm_number_node_create(pm_number_t *number, uint32_t value) {
number->length++;
pm_number_node_t *node = malloc(sizeof(pm_number_node_t));
*node = (pm_number_node_t) { .next = NULL, .value = value };
return node;
}
/**
* Add a 32-bit integer to a number.
*/
static void
pm_number_add(pm_number_t *number, uint32_t addend) {
uint32_t carry = addend;
pm_number_node_t *current = &number->head;
while (carry > 0) {
uint64_t result = (uint64_t) current->value + carry;
carry = (uint32_t) (result >> 32);
current->value = (uint32_t) result;
if (carry > 0) {
if (current->next == NULL) {
current->next = pm_number_node_create(number, carry);
break;
}
current = current->next;
}
}
}
/**
* Multiple a number by a 32-bit integer. In practice, the multiplier is the
* base of the number, so this is 2, 8, 10, or 16.
*/
static void
pm_number_multiply(pm_number_t *number, uint32_t multiplier) {
uint32_t carry = 0;
for (pm_number_node_t *current = &number->head; current != NULL; current = current->next) {
uint64_t result = (uint64_t) current->value * multiplier + carry;
carry = (uint32_t) (result >> 32);
current->value = (uint32_t) result;
if (carry > 0 && current->next == NULL) {
current->next = pm_number_node_create(number, carry);
break;
}
}
}
/**
* Return the value of a digit in a number.
*/
static uint32_t
pm_number_parse_digit(const uint8_t character) {
switch (character) {
case '0': return 0;
case '1': return 1;
case '2': return 2;
case '3': return 3;
case '4': return 4;
case '5': return 5;
case '6': return 6;
case '7': return 7;
case '8': return 8;
case '9': return 9;
case 'a': case 'A': return 10;
case 'b': case 'B': return 11;
case 'c': case 'C': return 12;
case 'd': case 'D': return 13;
case 'e': case 'E': return 14;
case 'f': case 'F': return 15;
default: assert(false && "unreachable");
}
}
/**
* Parse a number from a string. This assumes that the format of the number has
* already been validated, as internal validation checks are not performed here.
*/
PRISM_EXPORTED_FUNCTION void
pm_number_parse(pm_number_t *number, pm_number_base_t base, const uint8_t *start, const uint8_t *end) {
switch (*start) {
case '-':
number->negative = true;
/* fallthrough */
case '+':
start++;
break;
default:
break;
}
uint32_t multiplier;
switch (base) {
case PM_NUMBER_BASE_BINARY:
start += 2; // 0b
multiplier = 2;
break;
case PM_NUMBER_BASE_OCTAL:
start++; // 0
if (*start == 'o' || *start == 'O') start++; // o
multiplier = 8;
break;
case PM_NUMBER_BASE_DECIMAL:
if (*start == '0' && (end - start) > 1) start += 2; // 0d
multiplier = 10;
break;
case PM_NUMBER_BASE_HEXADECIMAL:
start += 2; // 0x
multiplier = 16;
break;
case PM_NUMBER_BASE_UNKNOWN:
if (*start == '0' && (end - start) > 1) {
switch (start[1]) {
case '0': case '1': case '2': case '3': case '4': case '5': case '6': case '7': start++; multiplier = 8; break;
case 'b': case 'B': start += 2; multiplier = 2; break;
case 'o': case 'O': start += 2; multiplier = 8; break;
case 'd': case 'D': start += 2; multiplier = 10; break;
case 'x': case 'X': start += 2; multiplier = 16; break;
default: assert(false && "unreachable");
}
} else {
multiplier = 10;
}
break;
}
for (pm_number_add(number, pm_number_parse_digit(*start++)); start < end; start++) {
if (*start == '_') continue;
pm_number_multiply(number, multiplier);
pm_number_add(number, pm_number_parse_digit(*start));
}
}
/**
* Recursively destroy the linked list of a number.
*/
static void
pm_number_node_destroy(pm_number_node_t *number) {
if (number->next != NULL) {
pm_number_node_destroy(number->next);
}
free(number);
}
/**
* Free the internal memory of a number. This memory will only be allocated if
* the number exceeds the size of a single node in the linked list.
*/
PRISM_EXPORTED_FUNCTION void
pm_number_free(pm_number_t *number) {
if (number->head.next) {
pm_number_node_destroy(number->head.next);
}
}