x86_64 (zero indexed, length given), 19 16 bytes
Raw machine code:
31 c0 57 f3 aa 5f 89 d1 8d c6 04 07 01 e2 f9 c3
Uncommented assembly:
.intel_syntax noprefix
.globl untruth
untruth:
xor eax, eax
push rdi
rep stosb byte ptr [rdi]
pop rdi
mov ecx, edx
.Lloop:
lodsd dword ptr [rsi]
mov byte ptr [rdi + rax], 1
loop .Lloop
.Lend:
ret
Explanation
I'm not too good at x86, so I am pretty sure there is a better way to do this.
C signature:
// System V ABI (rdi, rsi, rdx, rcx)
void untruth(bool *out, const uint32_t *indices, uint32_t indices_len, uint32_t out_len);
It's my function, I can order the parameters however I please. 😏
First: memset(out, 0, out_len) using rep stosb. Since we need to save the pointer and stosb clobbers it, we push and pop it.
The standard calling conventions say that the direction flag is always cleared when calling, so we know this will be a forwards operation.
untruth:
xor eax, eax
push rdi
rep stosb byte ptr [rdi]
pop rdi
Using the fancy loop instruction, loop through each index in the array, storing 1 to out[index]
mov ecx, edx
.Lloop:
lodsd dword ptr [rsi]
mov byte ptr [rdi + rax], 1
loop .Lloop
At the end of the loop, return.
.Lend:
ret
Note: It also happens to be x86-compatible on the binary level.
Thanks to Neil for the -3 bytes (using lodsd)!
x86_64 (zero indexed, calculates max), 28 bytes
Raw machine code:
31 c0 57 51 af 0f 42 47 fc e2 f9 91 56 56 5f f3
aa 5f 59 5e ad c6 04 07 01 e2 f9 c3
Assembly:
.intel_syntax noprefix
.globl untruth
# void untruth(const uint32_t *indices{rdi}, char *out{rsi}, uint32_t indices_len{rcx})
untruth:
xor eax, eax
push rdi
push rcx
.Lfind_max:
scasd eax, dword ptr [rdi]
cmovb eax, dword ptr [rdi - 4]
loop .Lfind_max
.Lfind_max.end:
xchg ecx, eax
push rsi
push rsi
pop rdi
rep stos byte ptr [rdi], al
pop rdi
pop rcx
pop rsi
.Lloop:
lodsd eax, dword ptr [rsi]
mov byte ptr [rdi + rax], 1
loop .Lloop
.Lloop_end:
ret
This version will check for the maximum itself, but the output buffer provided must be large enough.
Probably many things here can be optimized.
Explanation
Note that the parameters are different than the first: indices is in rdi, out is in rsi, rdx is unused, and indices_len is in rcx.
I don't know why scasd uses rdi but whatever.
This is a simple max loop. It compares each dword in indices, and sets eax to the maximum.
This seems to be smaller than doing something with lodsd, although that 4 byte cmovb is pretty yucky.
untruth:
xor eax, eax
push rdi
push rcx
.Lfind_max:
scasd eax, dword ptr [rdi]
cmovb eax, dword ptr [rdi - 4]
loop .Lfind_max
Since we know ecx will be zero due to the loop condition, we can set ecx to the maximum and set eax to zero in one byte.
.Lfind_max.end:
xchg ecx, eax
Unfortunately, our output array is in rsi, not rdi. We push and pop twice to mov without the REX tax and save a copy, then do a memset with rep stosb.
push rsi
push rsi
pop rdi
rep stos byte ptr [rdi], al
pop rdi
Now we need to get indices and indices_len from the stack. Note that this time, we put indices into rsi.
pop rcx
pop rsi
For each dword in indices, out[indices[i]] to 1 using lodsd and loop
.Lloop:
lodsd eax, dword ptr [rsi]
mov byte ptr [rdi + rax], 1
loop .Lloop
Return.
.Lloop_end:
ret
