Software APIs
memory.c
1// Copyright lowRISC contributors (OpenTitan project).
2// Licensed under the Apache License, Version 2.0, see LICENSE for details.
3// SPDX-License-Identifier: Apache-2.0
4
5#include "sw/device/lib/base/memory.h"
6
7#include <assert.h>
8#include <stdint.h>
9
10#include "sw/device/lib/base/macros.h"
11
12#ifdef OT_PLATFORM_RV32
13#define OT_PREFIX_IF_NOT_RV32(name) name
14#else
15#define OT_PREFIX_IF_NOT_RV32(name) ot_##name
16#endif
17
18static size_t compute_num_leading_bytes(const void *left, const void *right,
19 size_t len) {
20 if (len < alignof(uint32_t)) {
21 return len;
22 }
23 const size_t left_ahead = OT_UNSIGNED(misalignment32_of((uintptr_t)left));
24 const size_t right_ahead = OT_UNSIGNED(misalignment32_of((uintptr_t)right));
25 if (right == NULL || left_ahead == right_ahead) {
26 return (4 - left_ahead) & 0x3;
27 }
28 return len;
29}
30
31/**
32 * Compute the bounds of the word-aligned region for the given buffers.
33 *
34 * It's more efficient for our memory functions to operate on `uint32_t` values
35 * than individual bytes, but we can only read `uint32_t` values from aligned
36 * addresses. This function effectively breaks the given buffers into three
37 * consecutive chunks: the unaligned "head", the aligned "body", and the
38 * unaligned "tail".
39 *
40 * @param[in] left The memory function's first buffer argument. Cannot be NULL.
41 * @param[in] right The memory function's second buffer argument. May be NULL.
42 * @param[in] len The length in bytes of both `left` and `right.`
43 * @param[out] out_body_offset The start of the body region.
44 * @param[out] out_tail_offset The start of the tail region.
45 */
46static void compute_alignment(const void *left, const void *right, size_t len,
47 size_t *out_body_offset,
48 size_t *out_tail_offset) {
49 const size_t num_leading_bytes = compute_num_leading_bytes(left, right, len);
50 *out_body_offset = num_leading_bytes;
51
52 const size_t num_words = (len - num_leading_bytes) / sizeof(uint32_t);
53 *out_tail_offset = num_leading_bytes + num_words * sizeof(uint32_t);
54}
55
56static uint32_t repeat_byte_to_u32(uint8_t byte) {
57 const uint32_t word = byte;
58 return word << 24 | word << 16 | word << 8 | word;
59}
60
61void *OT_PREFIX_IF_NOT_RV32(memcpy)(void *restrict dest,
62 const void *restrict src, size_t len) {
63 if (dest == NULL || src == NULL) {
64 return dest;
65 }
66 unsigned char *dest8 = (unsigned char *)dest;
67 const unsigned char *src8 = (const unsigned char *)src;
68 size_t body_offset, tail_offset;
69 compute_alignment(dest, src, len, &body_offset, &tail_offset);
70 size_t i = 0;
71 for (; i < body_offset; ++i) {
72 dest8[i] = src8[i];
73 }
74 for (; i < tail_offset; i += sizeof(uint32_t)) {
75 uint32_t word = read_32(&src8[i]);
76 write_32(word, &dest8[i]);
77 }
78 for (; i < len; ++i) {
79 dest8[i] = src8[i];
80 }
81 return dest;
82}
83
84void *OT_PREFIX_IF_NOT_RV32(memset)(void *dest, int value, size_t len) {
85 unsigned char *dest8 = (unsigned char *)dest;
86 const uint8_t value8 = (uint8_t)value;
87
88 size_t body_offset, tail_offset;
89 compute_alignment(dest, NULL, len, &body_offset, &tail_offset);
90 size_t i = 0;
91 for (; i < body_offset; ++i) {
92 dest8[i] = value8;
93 }
94 const uint32_t value32 = repeat_byte_to_u32(value8);
95 for (; i < tail_offset; i += sizeof(uint32_t)) {
96 write_32(value32, &dest8[i]);
97 }
98 for (; i < len; ++i) {
99 dest8[i] = value8;
100 }
101 return dest;
102}
103
104enum {
105 kMemCmpEq = 0,
106 kMemCmpLt = -42,
107 kMemCmpGt = 42,
108};
109
110int OT_PREFIX_IF_NOT_RV32(memcmp)(const void *lhs, const void *rhs,
111 size_t len) {
112 const unsigned char *lhs8 = (const unsigned char *)lhs;
113 const unsigned char *rhs8 = (const unsigned char *)rhs;
114 size_t body_offset, tail_offset;
115 compute_alignment(lhs, rhs, len, &body_offset, &tail_offset);
116 size_t i = 0;
117 for (; i < body_offset; ++i) {
118 if (lhs8[i] < rhs8[i]) {
119 return kMemCmpLt;
120 } else if (lhs8[i] > rhs8[i]) {
121 return kMemCmpGt;
122 }
123 }
124 for (; i < tail_offset; i += sizeof(uint32_t)) {
125#if OT_BUILD_FOR_STATIC_ANALYZER
126 assert(&lhs8[i] != NULL);
127 assert(&rhs8[i] != NULL);
128#endif
129 uint32_t word_left = __builtin_bswap32(read_32(&lhs8[i]));
130 uint32_t word_right = __builtin_bswap32(read_32(&rhs8[i]));
131 static_assert(__BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__,
132 "memcmp assumes that the system is little endian.");
133 if (word_left < word_right) {
134 return kMemCmpLt;
135 } else if (word_left > word_right) {
136 return kMemCmpGt;
137 }
138 }
139 for (; i < len; ++i) {
140 if (lhs8[i] < rhs8[i]) {
141 return kMemCmpLt;
142 } else if (lhs8[i] > rhs8[i]) {
143 return kMemCmpGt;
144 }
145 }
146 return kMemCmpEq;
147}
148
149int memrcmp(const void *lhs, const void *rhs, size_t len) {
150 const unsigned char *lhs8 = (const unsigned char *)lhs;
151 const unsigned char *rhs8 = (const unsigned char *)rhs;
152 size_t body_offset, tail_offset;
153 compute_alignment(lhs, rhs, len, &body_offset, &tail_offset);
154 size_t end = len;
155 for (; end > tail_offset; --end) {
156 const size_t i = end - 1;
157 if (lhs8[i] < rhs8[i]) {
158 return kMemCmpLt;
159 } else if (lhs8[i] > rhs8[i]) {
160 return kMemCmpGt;
161 }
162 }
163 for (; end > body_offset; end -= sizeof(uint32_t)) {
164 const size_t i = end - sizeof(uint32_t);
165#if OT_BUILD_FOR_STATIC_ANALYZER
166 assert(&lhs8[i] != NULL);
167 assert(&rhs8[i] != NULL);
168#endif
169 uint32_t word_left = read_32(&lhs8[i]);
170 uint32_t word_right = read_32(&rhs8[i]);
171 static_assert(__BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__,
172 "memrcmp assumes that the system is little endian.");
173 if (word_left < word_right) {
174 return kMemCmpLt;
175 } else if (word_left > word_right) {
176 return kMemCmpGt;
177 }
178 }
179 for (; end > 0; --end) {
180 const size_t i = end - 1;
181 if (lhs8[i] < rhs8[i]) {
182 return kMemCmpLt;
183 } else if (lhs8[i] > rhs8[i]) {
184 return kMemCmpGt;
185 }
186 }
187 return kMemCmpEq;
188}
189
190void *OT_PREFIX_IF_NOT_RV32(memchr)(const void *ptr, int value, size_t len) {
191 const unsigned char *ptr8 = (const unsigned char *)ptr;
192 const uint8_t value8 = (uint8_t)value;
193
194 size_t body_offset, tail_offset;
195 compute_alignment(ptr, NULL, len, &body_offset, &tail_offset);
196 size_t i = 0;
197 for (; i < body_offset; ++i) {
198 if (ptr8[i] == value8) {
199 return (void *)&ptr8[i];
200 }
201 }
202 const uint32_t value32 = repeat_byte_to_u32(value8);
203 for (; i < tail_offset; i += sizeof(uint32_t)) {
204 uint32_t word = read_32(&ptr8[i]);
205 uint32_t bits_eq = ~(word ^ value32);
206 static_assert(__BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__,
207 "memchr assumes that the system is little endian.");
208 if ((bits_eq & UINT8_MAX) == UINT8_MAX) {
209 return (void *)&ptr8[i];
210 }
211 if (((bits_eq >> 8) & UINT8_MAX) == UINT8_MAX) {
212 return (void *)&ptr8[i + 1];
213 }
214 if (((bits_eq >> 16) & UINT8_MAX) == UINT8_MAX) {
215 return (void *)&ptr8[i + 2];
216 }
217 if (((bits_eq >> 24) & UINT8_MAX) == UINT8_MAX) {
218 return (void *)&ptr8[i + 3];
219 }
220 }
221 for (; i < len; ++i) {
222 if (ptr8[i] == value8) {
223 return (void *)&ptr8[i];
224 }
225 }
226 return NULL;
227}
228
229void *OT_PREFIX_IF_NOT_RV32(memrchr)(const void *ptr, int value, size_t len) {
230 const unsigned char *ptr8 = (const unsigned char *)ptr;
231 const uint8_t value8 = (uint8_t)value;
232
233 size_t body_offset, tail_offset;
234 compute_alignment(ptr, NULL, len, &body_offset, &tail_offset);
235
236 size_t end = len;
237 for (; end > tail_offset; --end) {
238 const size_t i = end - 1;
239 if (ptr8[i] == value8) {
240 return (void *)&ptr8[i];
241 }
242 }
243 const uint32_t value32 = repeat_byte_to_u32(value8);
244 for (; end > body_offset; end -= sizeof(uint32_t)) {
245 const size_t i = end - sizeof(uint32_t);
246 uint32_t word = read_32(&ptr8[i]);
247 uint32_t bits_eq = ~(word ^ value32);
248 static_assert(__BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__,
249 "memrchr assumes that the system is little endian.");
250 if (((bits_eq >> 24) & UINT8_MAX) == UINT8_MAX) {
251 return (void *)&ptr8[i + 3];
252 }
253 if (((bits_eq >> 16) & UINT8_MAX) == UINT8_MAX) {
254 return (void *)&ptr8[i + 2];
255 }
256 if (((bits_eq >> 8) & UINT8_MAX) == UINT8_MAX) {
257 return (void *)&ptr8[i + 1];
258 }
259 if ((bits_eq & UINT8_MAX) == UINT8_MAX) {
260 return (void *)&ptr8[i];
261 }
262 }
263 for (; end > 0; --end) {
264 const size_t i = end - 1;
265 if (ptr8[i] == value8) {
266 return (void *)&ptr8[i];
267 }
268 }
269 return NULL;
270}
271
272// `extern` declarations to give the inline functions in the corresponding
273// header a link location.
274
275extern ptrdiff_t misalignment32_of(uintptr_t);
276extern uint32_t read_32(const void *);
277extern void write_32(uint32_t, void *);
278extern uint64_t read_64(const void *);
279extern void write_64(uint64_t, void *);
280
281#undef OT_PREFIX_IF_NOT_RV32