mem: Use integer primitives for byte operations

5ad4470fa70da88fa793eb74f1b284dbdddf06e9817c4f45868ce5dfd76084c8
Copy and compare byte slices a word at a time. Use fixed-width loads
and stores for integer encoding, and delegate population counts to the
bit primitive.

Compare the first byte before word comparisons for inputs of at least
eight bytes. Keep short inputs in byte loops and start word comparisons
at offset zero.

Assisted-by: Codex:gpt-6
Change-Id: I016fce19d68429b05b68fce0f0b1f4b2866ffbed
Alexis Sellier committed ago 1 parent 3efd76cb
lib/std/arch/rv64/emit.rad +5 -4
1 1
//! RV64 binary emission.
2 2
//!
3 3
//! Emits RV64 machine code as `u32` list.
4 4
5 -
use std::lang::il;
5 +
use std::bits;
6 +
use std::collections::dict;
6 7
use std::lang::alloc;
7 -
use std::mem::heap;
8 8
use std::lang::gen;
9 9
use std::lang::gen::data;
10 10
use std::lang::gen::labels;
11 11
use std::lang::gen::types;
12 -
use std::collections::dict;
12 +
use std::lang::il;
13 13
use std::mem;
14 +
use std::mem::heap;
14 15
15 16
use super::encode;
16 17
17 18
/// Maximum number of instructions in code buffer.
18 19
constant MAX_INSTRS: u32 = 2097152;
184 185
    // so RA is never clobbered and doesn't need saving.
185 186
    if isLeaf and localSize == 0 and usedCalleeSaved == 0 {
186 187
        return frame;
187 188
    }
188 189
    // Compute total frame size. Includes RA and FP registers.
189 -
    let savedRegs = mem::popCount(usedCalleeSaved) + 2;
190 +
    let savedRegs = bits::popCount32(usedCalleeSaved) as i32 + 2;
190 191
    let savedSize = savedRegs * super::DWORD_SIZE;
191 192
    if localSize > MAX_I32_ADDR as i32 - savedSize - (super::STACK_ALIGNMENT - 1) {
192 193
        throw super::Error::Capacity(super::Limit::FrameSize);
193 194
    }
194 195
    let totalSize = mem::alignUpI32(localSize + savedSize, super::STACK_ALIGNMENT);
lib/std/mem.rad +68 -19
47 47
/// Copy bytes between two slices. Returns the number of bytes copied.
48 48
export fn copy(into: &mut [u8], from: &[u8]) -> u32 throws (MemoryError) {
49 49
    if into.len < from.len {
50 50
        throw MemoryError::BufferTooSmall;
51 51
    }
52 -
    for x, i in from {
53 -
        set into[i] = x;
52 +
    let mut i: u32 = 0;
53 +
    while from.len - i >= 8 {
54 +
        store64Le(into, i, load64Le(from, i));
55 +
        set i += 8;
56 +
    }
57 +
    while i < from.len {
58 +
        set into[i] = from[i];
59 +
        set i += 1;
54 60
    }
55 61
    return from.len;
56 62
}
57 63
58 64
/// Strip a byte-level prefix from the input, and return the suffix.
171 177
/// Align signed value up to alignment boundary.
172 178
export fn alignUpI32(value: i32, alignment: i32) -> i32 {
173 179
    return (value + alignment - 1) & ~(alignment - 1);
174 180
}
175 181
176 -
/// Count number of set bits in a 32-bit value.
177 -
export fn popCount(x: u32) -> i32 {
178 -
    let mut n = x;
179 -
    let mut count: i32 = 0;
180 -
    while n <> 0 {
181 -
        set count += (n & 1) as i32;
182 -
        set n >>= 1;
183 -
    }
184 -
    return count;
185 -
}
186 -
187 182
/// Check whether two byte slices have the same length and contents.
188 183
export fn eq(a: &[u8], b: &[u8]) -> bool {
189 -
    if a.len <> b.len {
184 +
    let len = a.len;
185 +
    if len <> b.len {
190 186
        return false;
191 187
    }
192 188
    unsafe {
193 189
        if a.ptr == b.ptr {
194 190
            return true;
195 191
        }
196 192
    }
197 -
    for i in 0 .. a.len {
198 -
        if a[i] <> b[i] {
193 +
    let mut i: u32 = 0;
194 +
    if len >= 8 {
195 +
        if a[0] <> b[0] {
196 +
            return false;
197 +
        }
198 +
        while len - i >= 8 {
199 +
            if load64Le(a, i) <> load64Le(b, i) {
200 +
                return false;
201 +
            }
202 +
            set i += 8;
203 +
        }
204 +
    }
205 +
    for index in i .. len {
206 +
        if a[index] <> b[index] {
199 207
            return false;
200 208
        }
201 209
    }
202 210
    return true;
203 211
}
208 216
export fn cmp(a: &[u8], b: &[u8]) -> i32 {
209 217
    let aLen = a.len;
210 218
    let bLen = b.len;
211 219
212 220
    let common = bLen if bLen < aLen else aLen;
213 -
    for i in 0 .. common {
214 -
        let aByte = a[i];
215 -
        let bByte = b[i];
221 +
    let mut i: u32 = 0;
222 +
    if common >= 8 {
223 +
        let aByte = a[0];
224 +
        let bByte = b[0];
225 +
        if aByte < bByte {
226 +
            return -1;
227 +
        }
228 +
        if aByte > bByte {
229 +
            return 1;
230 +
        }
231 +
        while common - i >= 8 {
232 +
            let aWord = load64Le(a, i);
233 +
            let bWord = load64Le(b, i);
234 +
            if aWord <> bWord {
235 +
                // The first byte has the most weight in a lexicographic comparison.
236 +
                return -1 if bits::byteSwap64(aWord) < bits::byteSwap64(bWord) else 1;
237 +
            }
238 +
            set i += 8;
239 +
        }
240 +
    }
241 +
    for index in i .. common {
242 +
        let aByte = a[index];
243 +
        let bByte = b[index];
216 244
        if aByte < bByte {
217 245
            return -1;
218 246
        }
219 247
        if aByte > bByte {
220 248
            return 1;
230 258
}
231 259
232 260
/// Write the low `size` bytes of `value` to `buf` at `offset` in little-endian
233 261
/// order. The caller checks that `buf` has room for `size` bytes.
234 262
export fn writeLe(buf: &mut [u8], offset: u32, value: u64, size: u32) {
263 +
    match size {
264 +
        case 2 => {
265 +
            store16Le(buf, offset, value as u16);
266 +
            return;
267 +
        }
268 +
        case 4 => {
269 +
            store32Le(buf, offset, value as u32);
270 +
            return;
271 +
        }
272 +
        case 8 => {
273 +
            store64Le(buf, offset, value);
274 +
            return;
275 +
        }
276 +
        else => {}
277 +
    }
235 278
    for i in 0 .. size {
236 279
        set buf[offset + i] = (value >> (i * 8) as u64) as u8;
237 280
    }
238 281
}
239 282
240 283
/// Read `size` bytes of `buf` at `offset` as a little-endian unsigned value.
241 284
/// The caller checks that `buf` holds `size` bytes at `offset`.
242 285
export fn readLe(buf: &[u8], offset: u32, size: u32) -> u64 {
286 +
    match size {
287 +
        case 2 => return load16Le(buf, offset) as u64,
288 +
        case 4 => return load32Le(buf, offset) as u64,
289 +
        case 8 => return load64Le(buf, offset),
290 +
        else   => {}
291 +
    }
243 292
    let mut value: u64 = 0;
244 293
    for i in 0 .. size {
245 294
        set value = value | (buf[offset + i] as u64 << (i * 8) as u64);
246 295
    }
247 296
    return value;