I’ve been wondering… what is:
%ifidn __OUTPUT_FORMAT__,elf64
section .note.GNU-stack noalloc noexec nowrite progbits
%endif
Perhaps could have a comment in lagana to explain and leave alone.
Bit-manipulation (Secrets)
Ooooh fun. I am a big fan of this and most of my solutions to secrets accross Exercism use bitwise operators. I start again with the work to define them functions so I can run the tests. I do notice some inconsistencies in the sub comments. Arguments are not listed as list, and the copy is slightly different in most functions.
Let’s get into it!
I read about immediate. I guess this is the “literal” we know from other languages. I do not recall if this was mentioned in an earlier concept.
extract_higher_bits
I am wondering what the canonical / idiomatic way to do this is. My intuition says:
- get the parameter
rdi (but then the 16bit size)
and with 0b1111111100000000
I see in the tests that I can write it with underscores:
0b1111_1111_0000_0000
About the and operator I read:
Most of them take two operands, perform a bitwise operation on both and store the result in the destination operand. The exception is not, which takes just one destination operand.
Yeah okay but which one is the destination operand? I would assume the first because add x, y has x as destination. I recall from computer science (which I studied long ago) that this was the difference between the two types. One had source before dest and one had dest before source.
Anyway. It’s easy to test:
mov ax, 0xFF
and di, ax
if this error with the result being 255 and the inverse errors with non-255, then and ax, di means and dest, src.
mov ax, 0xF0
and ax, di
Unfortunately this gives me Expected 164 Was 192.. I think that’s because I am now setting the 16bit register and it expects 8bits, which are ah/al. I don’t know how to do the conversion, but I re-read lasagna and see:
When using less than 64-bits, the bits accessed are usually from the lower portion of the register. The exception to this rule are ah , bh , ch and dh , which access the upper 8-bits from the 16-bits portion of the register.
So that means that if I can write 0000_0000_value to the 16bit register, and the test uses al, then I am golden.
What I need to accomplish is move the bits from di to the right, fill with zeros, and return that.
mov ax, di
shr ax, 8
extract_lower_bits
I think I can use the same trick here:
So either I and with 0x0F, or I shift left, then call extract_higher_bits. Since I don’t know yet how to make the and work here, I take the second approach:
shl di, 8
call extract_higher_bits
extract_redundant_bits
I think what I need to do is:
|
0 - 8 |
9 - 15 |
| di |
 |
|
| ax |
0 |
0-8 & 9-15 |
I already know how to get the higher and lower bits, and I know how to get only the 8 bits so I am in the right size right away (al instead of ax)
call extract_higher_bits
mov bl, al
call extract_lower_bits
and al, bl
Yay.
set_message_bits
From the instructions it’s not completely clear if high or low is the mask or message. However, the goal is: return 1 if mask is 1, otherwise keep the original bit in the message. That means: if either bit is 1, have the bit be 1, if neither bit is 1, have the bit be 0. That sounds like or
1100 0100 1100 0101
1100 0100
1100 0101
1100 0101 OR
1110 0101 EXAMPLE
Yeah I don’t think the example is correct. I am just going to try it.
call extract_higher_bits
mov bl, al
call extract_lower_bits
or al, bl
It worked! @oxe-b you probably want to update the example.
rotate_private_key
I believe I should start with extracting the redundant bits, and then:
- count the number of 1s
- take the private key
- rotate it left by that count
I’ll need popcnt which only works on 16-bit values;
I’ll need rol which only works with the second value being cl (or a literal).
That means I must zero-extend the redundant bits answer:
call extract_redundant_bits ; find redundant bits
movzx ax, al ; zero-extend answer to 16bits
popcnt cx, ax ; count number of 1s
The number in cx must live in cl as well, because there are only 16 bits to count. I don’t quite understand why this operation only takes the 16-bit arguments on both sides, but that’s besides the point.
At this moment I can still run the tests. Let me try to read the private key
section .data
PRIVATE_KEY equ 0b1011_0011_0011_1100
If it turns out I never update this, it can become .odata.
Then I try tor move it into the result (and then rol the result):
mov ax, word [PRIVATE_KEY] ; get private key
rol ax, cl ; rotate left by stored count
ret
That gives me a segmentation fault. Meh.
mov ax, 0b1011_0011_0011_1100 ; get private key
rol ax, cl ; rotate left by stored count
ret
This passes the tests. Okay. I supposed that LABEL equ value doesn’t give me memory addresses to play with, and the dq things do. I think I forgot what the concepts say about that, but I can try to inline the label directly:
mov ax, PRIVATE_KEY ; get private key
rol ax, cl ; rotate left by stored count
ret
Superb. Two more to go!
format_private_key
I think this is called after the key is already rotated, so no need to rotate the key.
- Isolate the lowest 8-bit portion of the rotated private key, which is the base value. That means extract_lowest_bits
- Isolate the highest 8-bit portion of the rotated private key, which is a mask to be applied to the base value. That means extract_highest_bits
- Flip set bits in the base value that are also set in the mask. That is exclusive or
- Flip all bits in the result.: That is not
call extract_higher_bits ; get the mask
mov bl, al
call extract_lower_bits ; get the base value
xor al, bl ; flip what's set in both
not al ; flip it
That does not pass any tests, but I am pretty certain it’s correct.
Perhaps my interpretation that it was already rotated (please add a note to the instructions) is wrong. Easy peasy lemon squeezy:
call rotate_private_key
mov di, ax
One more to go 
decrypt_message
I think it’s a bit hidden that encoding both the message and a mask is the input argument. I found the same text for other instructions, so I know I need to pass it into format_private_key, but I do think the stub can be improved to clearly indicate what is being passed in where.
I have to start with generating that private key, because that needs to be returned in the result.
Now wondering: are the registers for rdi preserved across calls or no? In other words, if I am in function A, call function B which changes rdi, does it get changes in function A? I remember reading something about preserving but I do not recall. Let me look it up.
Some of those registers must be preserved across function calls: rbp, rsp, rbx, r12, r13, r14 and r15. Failing to preserve them may lead to an error or to undefined behaviour.
The others are not preserved and may be used freely: rax, rcx, rdx, rdi, rsi, r8, r9, r10 and r11.
That doesn’t answer my question. I’ll play it save and:
- explicitly store
rdi
- explicitly set
rdi before a call if needed
mov r8w, di ; store original input
call format_private_key ; get private key
mov r9b, al ; store private key
The instructions are not really clear on what needs to be happening, but reading back to set_message_bits I can see that that takes a message-mask combination and “set the relevant bits”. Let’s use that:
mov di, r8w ; prepare set bits
call set_message_bits
I do not understand how I am decrypting the message, or what that means, but if I ignore that gap, I take the instructions at face value and prepare the following:
- expand the message with 0s on the left
- expand the private key with 0s on the right
OR both, values to get the result
The first I can do with movzx ax, al.
The second I can do with shl <>, 8.
; Combine the two
movzx ax, al ; zero-fill output on the left (high)
shl r9w, 8 ; shift left private key (left fill)
or ax, r9w ; combine
And that concludes the exercise!
Takeaways
By far the exercise where I got stuck the least. A few things you already know about, and some more:
- Stub could be more consistent with the others, more explicit about the contents of the arguments
- It is (still) unclear to me, how you can “make smaller” a register, but I have a feeling it’s clearing the higher bits and that’s it. It was easier for me to use shift left and right in the first two tasks. Don’t know if that was intended
- The
equ thing you know about
- Final exercise could explicitly state that you don’t need to “understand decryption” or something similar
- Fixing the example for
OR
How did I do?
. I guess that’s expected!