2

I'm working with x86 Assembly and I've come accross the need to use the MUL instruction.

My code fragment used to be this:

mov al, <some_number>
mul bl
add al, [edi]
mov [edi], al

Where the <some_number> is a constant defined outside this Assembly fragment, it can be positive or negative. The bl register is set earlier in the code, it's always positive (as it just overflows/underflows whenever fit). I can also probably optimize the last two statements to add [edi], al but I'm not 100% sure so I won't do that just yet.

So my program is hitting undefined behavior, in this case an infinite loop, after checking what could be wrong for a long time I figured that I had to use IMUL because <some_number> could be negative.

But now it still doesn't work. Then I looked again in the manual and I saw that mul bl actually stores the result in ax. So I have a signed result in ax, while I want an unsigned (with overflow/underflow) result in al.

So my question is: How do I turn the signed result in ax in to an unsigned one in al? Basically the opposite of sign-extending.

Note: I've included my thought process here as well because it's quite likely that I'm doing things not as intended and that therefore I couldn't find an answer so far.

zx485
  • 28,498
  • 28
  • 50
  • 59
skiwi
  • 66,971
  • 31
  • 131
  • 216
  • 4
    The opposite of sign-extension (if it can be called that) is just truncation. Which is already what you're doing. So if that isn't right, please explain what *should* happen – harold Nov 29 '16 at 21:27
  • @harold I'm confused about part. If I have a negative 16-bit number then the MSB will be 1, correct? If I then proceed to only use the lower 8-bits, then I've essentially completely lost the sign bit, haven't I? – skiwi Nov 29 '16 at 21:29
  • 1
    There are no branches in this code so what is the loop you're having trouble with? More context will help. As harold said, if ax is a signed integer extended from an 8-bit integer, then al already holds what you want. – Andrew Nov 29 '16 at 21:29
  • @skiwi If the number is negative, sign extension means all of the bits from the 8th to the 16th will also be 1; truncating to the lower 8 bits will be the same value. – Andrew Nov 29 '16 at 21:30
  • @Andrew Sorry for not providing more context, but I'm working on a compiler that converts Brainfuck code to Assembly, it's a bit hard to get a working example from that. Basically I had a working version, then I optimized some loops and now it's broken, but only on some programs, so I'm trying to figure out what could be the issue. There's no way I could post it on SO though until I located the issue. – skiwi Nov 29 '16 at 21:32
  • 1
    Truncation destroys the sign only in (some of the) cases that the result cannot be represented in the smaller number of bits anyway, and in that case it gives you a wrapped result (even then the sign can be the same, of course, but that doesn't mean much). Or you could saturate instead of truncate. I can't think of any thirds option that makes any sense – harold Nov 29 '16 at 21:37
  • @harold I think I understand the truncation now. Therefore the premises of the question indeed does not make sense. This left me wondering though: How can an add between a signed and an unsigned number work? As I see it they have completely different representations. I'm working with only unsigned numbers in my code, only `` and the result of imul are the odd ones. – skiwi Nov 29 '16 at 21:47
  • @skiwi You are correct. You cannot add a signed number with an unsigned number and expect the result to always make sense. You have to convert one of the numbers first so that they use the same representation. – Andrew Nov 29 '16 at 21:54
  • Why not just NEG it? Example : -5 x 10 = -50 (0xFFCE), neg 0xFFCE = 0x32 (50), it fits in AL. Assembly version : `mov bl,-5` , `mov al,10` , `imul bl` , `neg ax` . Or am I missing something in the question? – Jose Manuel Abarca Rodríguez Nov 29 '16 at 21:58
  • @Andrew I may be going the wrong way about this, but is there no instruction for converting from signed to unsigned? Google gave me no satisfactory results. – skiwi Nov 29 '16 at 21:59
  • 3
    @skiwi if you're going to truncate to the width of the input anyway, then you can just add them as-is. Extending, adding, then truncating, is the same as just adding (as long as the truncate truncates by enough). Signed and unsigned aren't representations, they're interpretations. – harold Nov 29 '16 at 22:01
  • @JoseManuelAbarcaRodríguez `bl` can be positive too, so that won't work – skiwi Nov 29 '16 at 22:04
  • You can make an " if " . – Jose Manuel Abarca Rodríguez Nov 29 '16 at 22:04
  • Can we back up here a bit, this whole thing makes less and less sense. Especially with that random negation thrown in. What is going in and what should come out? "How signed" is that multiplication? (eg a multiplication that keeps only the low half of the result is neither signed nor unsigned, it's just a plain bitvector multiplication with no inherent interpretation) – harold Nov 29 '16 at 22:09
  • *"but is there no instruction for converting from signed to unsigned?"* No, there is not. The registers just hold bits, they don't care how you interpret those bits. That's why, for example, you have an arithmetic-shift-right instruction (SAR) and a logical-shift-right instruction (SHR). SAR is used for signed numbers, and SHR is used for unsigned. For instructions like ADD, the flags (e.g. the overflow flag) give you information that can be interpreted differently depending on whether you think the values being added were signed or unsigned. – user3386109 Nov 29 '16 at 22:31
  • 1
    Can you like gather some example of input values, real output, and your guess what would look like correct output? It's sort easy to get out of 8b with IMUL, especially with `signed char`, as it's only 7b absolute value, so just `15*16` will throw it off already. – Ped7g Nov 30 '16 at 02:13
  • *hitting undefined behavior*. I'd be very surprised. In assembly language, [almost everything is exactly defined](http://stackoverflow.com/questions/40565835/is-integer-overflow-undefined-in-inline-x86-assembly). You've probably just written an infinite loop which is guaranteed to run the same way on every x86 CPU. This is a bug, but not UB. – Peter Cordes Nov 30 '16 at 06:37
  • You're using `bl` it as an operand for MUL, unsigned multiplication, so the bits in it and `al` are being interpreted as unsigned, producing an unsigned result in AX. So saying that *`bl` is always positive* is exactly equivalent to saying it's non-zero, because the unsigned interpretation of a bit-pattern is *always* non-negative. Can you write in C something that expresses what you want? And like Ped7g said, give some sample inputs / outputs. Because the answer to the question is `movzx ax, al` or `and ax, 0xFF`, or just read `al`, but that doesn't seem to be what you want. – Peter Cordes Nov 30 '16 at 06:42
  • Don't forget that `al` is just the lower 8 bits of `ax`. – puppydrum64 Dec 12 '22 at 16:13

2 Answers2

3

I was unable to properly understand the question and the follow up in the comments. Let me know if this isn't an answer at all.

I also figured out that this answer may be a clone of @Jose's one, so I'm considering removing it, specially if I turns out I misunderstood the question.

With imul bl we either have:

  1. The result of AL * BL fits into AL (but the result is sign extended to AX).
  2. The result of AL * BL doesn't fit into AL.

In the latter case you have to choose what to do.
In general you have to scale the result back to 8 bits, this can be as simple as solving the proportion 216:28 = AX : AL for AL or can be more involved (including not being a scale or any linear operation at all).

In the former case we need to compute the absolute value of the result.
Since case 1 assumes that the result fits AL, the register AH is either all zeros or all ones, matching the sign bit of AL.

imul bl           ;Original code

xor al, ah        ;NOT AL iif the result is negative
sub al, ah        ;AL = AL - (-1) = AL + 1 iif the result is negative

This exploits the well known identity, in twos' complement, neg(x) = not(x) + 1.

Peter Cordes
  • 328,167
  • 45
  • 605
  • 847
Margaret Bloom
  • 41,768
  • 5
  • 78
  • 124
  • IMUL sets OF and CF if `full_result != sign_extend(low_half_result)`, so you can detect case 1 vs. case 2 by branching on CF or OF as set by IMUL. See [this related question](http://stackoverflow.com/a/38254324/224132) for more discussion about IMUL's flag-setting, for the opposite problem: using 2-operand IMUL r64,r64 and still detecting *unsigned* wraparound of the 64-bit low-half result. (tl;dr: just use MUL r64 which sets flags as needed for that.) – Peter Cordes Nov 30 '16 at 10:36
  • 1
    Also, I agree the question is highly problematic. I don't see how the OP can be sure that a signed interpretation of BL is "always positive" if it could have overflowed. The OP may really want to zero-extend BL (unsigned) and sign-extend AL (signed). Upvoted this for clearly explaining the 2 possible outcomes, and that taking the absolute value of AL probably isn't the Right Answer if the result doesn't fit. – Peter Cordes Nov 30 '16 at 10:45
  • @Peter, I consider the two cases mutually exclusive: The OP either can rule out case 1 or they can't. If they can't, they are probably missing something and the question has no answer. If they can, then taking the abs of *AL* may solve their problem. – Margaret Bloom Nov 30 '16 at 10:56
  • Hmm, good point, detecting overflow at runtime might not be useful. I guess I was thinking that you'd handle it by returning an error, not by getting a sane result. – Peter Cordes Nov 30 '16 at 11:09
1

This is my point of view in an example : if the result of multiplication is negative you NEG it, if it is positive you don't NEG it (I'm running this code in one of my compilers):

    mov bl, -5          ;◄■■ NEGATIVE NUMBER.
    mov al, 10
    imul bl             ;◄■■ AX = -50 (0xFFCE).

    cmp ax, 0
    jl  negative        ;◄■■ IF AX <  0 JUMP TO NEGATIVE.
    jmp continue        ;◄■■ IF AX >= 0 SKIP NEGATIVE.

negative:
    neg ax              ;◄■■ AX => POSITIVE (0xFFCE => 0x32).

continue:
Jose Manuel Abarca Rodríguez
  • 10,206
  • 3
  • 31
  • 38
  • 3
    You can write that more efficiently with a JNL to jump over the NEG, so one of the paths has no taken branches. (And of course [there are branchless ways to get the absolute value of an integer](https://godbolt.org/g/eV52mE)) – Peter Cordes Nov 30 '16 at 05:55