Jump to content
IGNORED

Unsigned comparisons with 8-bit variables


DZ-Jay

Recommended Posts

The IntyBASIC manual claims that 8-bit variables are unsigned by default, but it seems that testing them in a logical comparison induces the compiler to generate a signed test-and-branch instruction. :(

 

Is there a way to induce the compiler to treat the expression as unsigned?

 

Example Case:

Dim Var8

Var8 = 0

  ' ... some code ...

  If ((Var8 - 1) < 3) Then
    ' Out of range ...
  End If

 

The above assembles into the following code (annotated for legibility):

    MVI     var_VAR8,   R0      ; \
    DECR    R0                  ;  |_ If ((Var8 - 1) < 3) Then
    CMPI    #3, R0              ;  |
    BGE     T7                  ; /
    ; Out of range ...
T7:                             ; - End If

 

Notice the signed branching test (BGE).  Adding the statement "Unsigned Var8" does nothing (since presumably the variable is already unsigned).

 

If I change to an unsigned 16-bit:

Dim #Var16
Unsigned #Var16

#Var16 = 0

  ' ... some code ...

  If ((#Var16 - 1) < 3) Then
    ' Out of range ...
  End If

 

The assembled code changes to (annotated for legibility):

    MVI     var_&VAR16, R0      ; \
    DECR    R0                  ;  |_ If ((Var8 - 1) < 3) Then
    CMPI    #3, R0              ;  |
    BC      T7                  ; /
    ; Out of range ...
T7:                             ; - End If

 

Notice the rightly selected unsigned branching test (BC).

 

This looks to be a bug, but I was hoping someone had a work-around.  Any ideas?

 

     -dZ.

Link to comment
Share on other sites

I had a similar (but not identical) problem with INTLE, where (A > B) when A and B were both 16-bit unsigned variables was being treated as true when A = B.  My work around there was to reverse the comparison, using (B < A).  So you might try different relations (>, >=, etc) to see if any work.

 

In general I've found IntyBasic to have a variety of quirks, not only with signed/unsignedness, but also 8 vs 16 vs 32 bit operations.

In a language like C, mixing operands of different sizes and different signed/unsignedness has well defined behavior.  But with IntyBasic

it seems a little more ad hoc.  What is the signedness and size (8 vs 16 bits) of a constant, such as 1 or 255?  I don't know.  Under the

hood I think IntyBasic generally uses 16-bit operations, so 8-bit values are promoted to 16 bits.  And when signed and unsigned operands

are mixed, unsigned is supposed to win.

 

The attached bugs.bas/bugs.rom is a small program I sent to @nanochess demonstrating some of the issues I've seen.

I hesitate to call them bugs, actually, because I would first need to see the expected behavior well defined.

 

One other thing I pointed out to nanochess is that certain unary operations do not chain.

For example, this will give a compilation error:

 

    X1 = NOT -5 ' OK
    X2 = NOT NOT -5
    X3 = NOT NOT NOT -5

 


 

 

bugs.bas bugs.rom

Link to comment
Share on other sites

1 hour ago, Peripheral said:

I had a similar (but not identical) problem with INTLE, where (A > B) when A and B were both 16-bit unsigned variables was being treated as true when A = B.

 

I think that has been corrected.  At least I haven’t seen that in the generated assembly code when working with unsigned comparisons.  It seems to work correctly — but only when they are 16-bit variables.

 

1 hour ago, Peripheral said:

My work around there was to reverse the comparison, using (B < A).  So you might try different relations (>, >=, etc) to see if any work.


 


In my case is that signed and unsigned comparisons require different CPU test-and-branch instructions, and the compiler is always choosing the signed ones for 8-bit variables.

 

(The difference is that unsigned branch instructions interpret the carry and overflow flags differently, since there is no actual sign.)

 

 

1 hour ago, Peripheral said:

In general I've found IntyBasic to have a variety of quirks, not only with signed/unsignedness, but also 8 vs 16 vs 32 bit operations.

 

Personally, I have not noticed much issues.  The CPU uses 16-bit registers so all variables are treated as such internally.  Because 8-bit variables do not stretch all the way to the most-significant-bit (i.e., the sign bit), it makes sense to treat them as unsigned.  Conversely for the 16-bit variables.
 

The “signness” of variables should only affect sign propagation upon shifting right, and logical comparisons.  Unfortunately the former is completely ignored by the compiler (always shifting logically when dividing by powers of 2, irrespective of “signness”), and the latter only works for 16-bit variables.

 

The first one is a current compiler limitation, and is clearly described in the manual as such.  The last one is obviously a bug (or an undocumented limitation).

 

1 hour ago, Peripheral said:

In a language like C, mixing operands of different sizes and different signed/unsignedness has well defined behavior.  But with IntyBasic

it seems a little more ad hoc.

 

I am not sure that is true (regarding IntyBASIC).  Again, I haven’t experienced such ad hoc behaviour.  Do not misunderstand me:  the compiler has some issues and quirks — I just haven’t experienced all that many.

 

Generally, what I’ve observed is that special “signness” is only relevant in the context of variables, and is due specifically to the difference between 16-bit and 8-bit storage — the latter requires additional operations to extend the sign, which can get costly, so it makes sense to try to avoid it.

 

And … everything else is a 16-bit signed value.  That includes constants, macros, logical values, etc.

 

1 hour ago, Peripheral said:

What is the signedness and size (8 vs 16 bits) of a constant, such as 1 or 255? 
 

 

Easy: 16-bit signed.  Next!

 

The CP-1610 is a 16-bit CPU, with some affordances to support 8- and even 10-bit data.  Registers are 16-bit, bus is 16-bit, address space is 16-bit; but instructions are 10-bits (so that they can fit in 10-bit memory), and some attached devices are 8-bit (video and sound devices).

 

1 hour ago, Peripheral said:

Under the

hood I think IntyBasic generally uses 16-bit operations,

 

It does.

 

1 hour ago, Peripheral said:

so 8-bit values are promoted to 16 bits. 

 

The are.

 

1 hour ago, Peripheral said:

And when signed and unsigned operands

are mixed, unsigned is supposed to win.

 

I think it is the other way around in IntyBASIC (see my previous comments above):  everything is signed unless specifically told otherwise, by employing a 16-bit variable explicitly declared as unsigned.

 

The exception should be 8-bit variables which are unsigned by default, but logical comparisons do not consider this (as mentioned above).

 

That means that to IntyBASIC, the “unsigness” of 8-bit variables only means that the sign will not be extended upon retrieval from memory to a register — that is, assigning a negative value to an 8-bit variable will truncate its upper byte, not only losing its sign but corrupting the value — i.e., it is now a 16-bit 2’s complemented rendition of the original value, masquerading as a positive 8-bit value; like -1 ($FFFF) looking like 255 ($00FF).

 

1 hour ago, Peripheral said:

The attached bugs.bas/bugs.rom is a small program I sent to @nanochess demonstrating some of the issues I've seen.

I hesitate to call them bugs, actually, because I would first need to see the expected behavior well defined.

 

I’ll take a look when I get home.

 

1 hour ago, Peripheral said:

One other thing I pointed out to nanochess is that certain unary operations do not chain.

For example, this will give a compilation error:

 

    X1 = NOT -5 ' OK
    X2 = NOT NOT -5
    X3 = NOT NOT NOT -5

 

If it is a compilation error (as opposed to an assembler error), it could be that the precedence of the NOT operator is not handled correctly.  Does it work when surrounded by parentheses, like the following?

 

X1 = NOT (NOT -5)

 

Anyway, thanks for responding.  I’ll take a look at the sample file you provided later today.

 

   dZ.

Link to comment
Share on other sites

1 hour ago, DZ-Jay said:

 

I think that has been corrected.  At least I haven’t seen that in the generated assembly code when working with unsigned comparisons.  It seems to work correctly — but only when they are 16-bit variables.se is that signed and unsigned comparisons require different CPU test-and-branch instructions, and the compiler is always choosing the signed ones for 8-bit variables

 

I don't think any of the issues I've found have been corrected, since the IntyBASIC sources in nanochess' github repository haven't been touched in three years.  Of course it's possible he uses a different repository now.

 

Regarding the mixing of signs, here's the code in IntyBASIC that handles that:

    //
    // Mix signedness
    //
    int mix_signedness(int type1, int type2)
    {
        return type1 | type2;   // Unsigned wins
    }
 

So in your code, for example, Var8 is unsigned, 1 is (presumably) signed, and so (Var8 - 1) is unsigned.

 

I understand all the signedness and 8/16 bit issues.  The 32-bit issue arises because internally

the IntyBASIC compiler represents constant values with the C++ type "int", which is generally 32 bits

on today's platforms.  So when it does constant folding, it should really clamp those values

to 16 bits, especially in cases when the sign of the result is relevant.  But bugs.bas exposes

some places where it does not, and hence computes an unexpected result, or at least a result

different than what the hardware would produce.

 

Link to comment
Share on other sites

On 4/24/2023 at 1:45 PM, Peripheral said:

I don't think any of the issues I've found have been corrected, since the IntyBASIC sources in nanochess' github repository haven't been touched in three years.  Of course it's possible he uses a different repository now.

 

Regarding the mixing of signs, here's the code in IntyBASIC that handles that:

    //
    // Mix signedness
    //
    int mix_signedness(int type1, int type2)
    {
        return type1 | type2;   // Unsigned wins
    }


That is consistent with what I said.  It may seem significant to say “when mixing signs, unsigned wins,” but in practice, there are very narrow cases to which the sign comes into play in the context of the Intellivision — particularly shifting and conditional branching.  Of these, the IntyBASIC compiler handles only one, and it is not very consistent.

 

In other words, in the context of an IntyBASIC source code module, you can assume categorically that everything is signed by default, unless explicitly told to do otherwise.

 

The only way to explicitly tell the compiler to do otherwise is to declare a variable as unsigned and using it in an expression.  16-bit variables require the use of the “unsigned” directive, and 8-bit variables are ostensibly unsigned by default.

 

Nothing else can be made “unsigned” explicitly, only by involving an unsigned variable — and only within the context of a logical comparison.

 

Except that it only seems to work with 16-bit variables. DOH!

 

The only significance of the sign for 8-bit variables seems to be to induce the compiler to extend the sign bit when reading them from memory into a register — nothing else.  Involving them in an expression changes nothing in the generated assembly (with respect to the sign).


Everything else that is not a variable (constants, etc.) is signed.  And there is no way to induce the compiler to do otherwise — unless you involve an unsigned 16-bit variable in some fashion.
 

On 4/24/2023 at 1:45 PM, Peripheral said:

So in your code, for example, Var8 is unsigned, 1 is (presumably) signed, and so (Var8 - 1) is unsigned.

 

True, it should.  Except that it does not work.  The unsigness of “Var8” is ignored when compiling the comparison into a test-branch operation.
 

If I replace it with a 16-bit variable explicitly declared as unsigned, it works:  the compiler generates assembly code with the correct unsigned test-branch instructions.

 

On 4/24/2023 at 1:45 PM, Peripheral said:

I understand all the signedness and 8/16 bit issues.  The 32-bit issue arises because internally

the IntyBASIC compiler represents constant values with the C++ type "int", which is generally 32 bits

on today's platforms.  So when it does constant folding, it should really clamp those values

to 16 bits, especially in cases when the sign of the result is relevant. But bugs.bas exposes

some places where it does not, and hence computes an unexpected result, or at least a result

different than what the hardware would produce.

 


I haven’t had a chance to take a look at your sample module.  I’ll look at it tonight.

 

I do have some memories of the compiler giving me the wrong values when dealing with complex arithmetic expressions with constants within a DEF FN macro.  I believe those are due to the 32-bit/16-bit discrepancy between the compiler internal operations and it’s output.  That may be related to the quirks you are taking about.

 

However, I would separate those from the ones I have reported in this thread.  Quirks when handling constant expressions are distinct from quirks generating incorrect assembly code.

 

    dZ.

Link to comment
Share on other sites

On 4/24/2023 at 11:24 AM, Peripheral said:

I had a similar (but not identical) problem with INTLE, where (A > B) when A and B were both 16-bit unsigned variables was being treated as true when A = B.  My work around there was to reverse the comparison, using (B < A).  So you might try different relations (>, >=, etc) to see if any work.

 

In general I've found IntyBasic to have a variety of quirks, not only with signed/unsignedness, but also 8 vs 16 vs 32 bit operations.

In a language like C, mixing operands of different sizes and different signed/unsignedness has well defined behavior.  But with IntyBasic

it seems a little more ad hoc.  What is the signedness and size (8 vs 16 bits) of a constant, such as 1 or 255?  I don't know.  Under the

hood I think IntyBasic generally uses 16-bit operations, so 8-bit values are promoted to 16 bits.  And when signed and unsigned operands

are mixed, unsigned is supposed to win.

 

The attached bugs.bas/bugs.rom is a small program I sent to @nanochess demonstrating some of the issues I've seen.

I hesitate to call them bugs, actually, because I would first need to see the expected behavior well defined.

 

One other thing I pointed out to nanochess is that certain unary operations do not chain.

For example, this will give a compilation error:

 

    X1 = NOT -5 ' OK
    X2 = NOT NOT -5
    X3 = NOT NOT NOT -5

 


 

 

bugs.bas 7.44 kB · 1 download bugs.rom 6.57 kB · 1 download

 

Wow!  I just took a quick look at that.  I had encountered some of those -- particularly the ones with constants, which are not transported correctly from 32-bit to 16-bits -- but not the others.  Unsigned comparisons appear to be very broken indeed.

 

The unsigned constant issue can be easily worked-around by always truncating the expression results yourself.  For instance, the "testmod" can be easily fixed like this:

    #answer = 7 % (($FFFE + 4) And $FFFF)

 

The compiler will evaluate the entire thing to 1 (correct), and assigned that constant to #answer.

 

I was also intrigued by the test "testunsignedgt16."  I can see why it's not working.  When retaining the result of a logical expression, it always tries to default to true (-1) and change to false (zero) upon a failed test.  However, when comparing ">" on unsigned values, it includes the wrong instruction.

 

The correct test for unsigned "greater-than" should be Z=0, C=1 -- that is, the Zero flag is clear and the Carry flag is set.

 

Here's the compiled assembly for "testunsignedgt16," annotated for convenience:

    ;[251]     #answer = (#u16 > #u16_2)
    SRCFILE "bugs.bas",251
    CMP     var_&U16_2, R0          ; Compare both values
    MVII    #65535,     R0          ; Default to "true"
    BEQ     T30                     ; Z=1 ... true?? (Fail!)
    BC      T30                     ; C=1 ... true
    INCR    R0                      ; Anything else = false
T30:                                ;
    MVO     R0,     var_&ANSWER     ; Store result

 

Notice that the test for zero is wrong.  By defaulting to true and jumping out when the zero flag is set but before testing the carry flag, it results in the wrong answer.  If I was writing the assembly by hand, I probably would default to false (zero), and branch out whenever the Zero flag is true or the Carry flag is false; changing to -1 on the fall-through.  Otherwise, the tests become more complex and more branchy, which is never a good thing.

 

When you use the same comparison in a conditional branch, however, it works correctly:

    ;[254]     If (#u16 > #u16_2) Then
    SRCFILE "bugs.bas",254
    MVI     var_&U16,   R0          ; \_ Compare both values
    CMP     var_&U16_2, R0          ; /
    BEQ     T31                     ; Z=1 ... false (Yay!)
    BNC     T31                     ; C=0 ... false (Yay!)

    ; Some code here ...            ; Test is true, execute conditional block

    ;[256]     End If
    SRCFILE "bugs.bas",256
T31:

 

It is very similar to the code above, except that it works this time because the zero flag being set (==) will skip the conditional block, as will the carry flag not being set also.

 

This is the reason I haven't encountered many of these issues:  I tend to avoid assigning logical expression results to variables, because I am not fond of the extra cost of the extra branching to manage the logical value (0, -1).

 

Unfortunately, this flawed handling of logical values occurs not only when assigning it to a variable, but also when chaining multiple logical expressions using arithmetic or logical operators.  So, for instance, something like:

If (#u16 > #u16_2) And (#answer = 1) Then

 

Will result in the first term giving the wrong answer.

 

So, to work-around all these quirks, you need to code defensively in IntyBASIC.  My recommendations are:

  • Always truncate unsigned constant values to 16-bits to force the compiler to treat them as such.  E.g., "CONST Foo = (some-unsigned-constant) And $FFFF"
  • Avoid assigning unsigned logical expressions to a variable; use IF/ELSE to manage the branching yourself.
  • Avoid chaining unsigned logical expressions into larger expressions using arithmetic or logical operators; use nested IF/ELSE instead of "And," and multiple IF blocks instead of "Or," etc.

I just happen to have been doing this myself, mainly to avoid some of the extra memory round-trips and additional instructions IntyBASIC generates for some of its code; and I've managed to avoid encountering almost of those quirks in your tests.

 

Good job in preparing that test -- it is very thorough.

 

    -dZ.

 

Link to comment
Share on other sites

One thing I forgot to mentioned, in case it wasn't clear from the assembly code:  Single-term logical expressions in an "IF" conditional always generate test and branch code to either execute the conditional block, or skip over it.

 

Multi-term logical expressions -- or expressions assigned to a variable -- induce IntyBASIC to generate additional code to produce a logical truth value, either 0 or -1.  This is the case that causes most of the tests in the "bugs.bas" program to fail.

 

The work-around, as I suggested above is to avoid these sort of tests.  Your IF/ELSE blocks may become more nested and your code more verbose, but it will work correctly.

 

    -dZ.

Link to comment
Share on other sites

  • 1 month later...
On 4/24/2023 at 11:03 PM, DZ-Jay said:

So, to work-around all these quirks, you need to code defensively in IntyBASIC.  My recommendations are:

  • Always truncate unsigned constant values to 16-bits to force the compiler to treat them as such.  E.g., "CONST Foo = (some-unsigned-constant) And $FFFF"
  • Avoid assigning unsigned logical expressions to a variable; use IF/ELSE to manage the branching yourself.
  • Avoid chaining unsigned logical expressions into larger expressions using arithmetic or logical operators; use nested IF/ELSE instead of "And," and multiple IF blocks instead of "Or," etc.

 

And while we're offering tips, here are a few more:

 

Tip #1:

Comparisons to zero are much more efficient than to other constants, and comparisons equal to or less than zero are the best.  Try to express loop and other logical conditions as comparisons to zero.

 

For example, if your loop counts down to zero, and you want it to stop when it reaches zero, it is more efficient to use something like:

Loop Until (MyVar = 0)

 

Than to use,

Loop While (MyVar > 0)

 

Logically they are different expressions, but in practice both do exactly the same thing:  exit the loop when MyVar reaches zero.  The difference is that the first one is slightly faster in terms of CPU cycles.

 

The reason for this is that the CPU has a specialized instruction that tests if a value is zero or negative, while the second example requires a general constant comparison instruction which costs a couple more cycles.  It may not be much in isolation, but these savings add up -- especially in a loop, where the savings apply to each iteration.

 

Tip #2:

Counting down to zero is more efficient than counting up to some other number.

 

This is actually a variation of the first tip:  a counting loop needs to increment or decrement its control variable and compare it against the limit, then repeat or exit depending on the result.  As mentioned in the previous tip, if the comparison is against zero, the generated code will be slightly more efficient.


Note that in the latest version of IntyBASIC, this tip only works on DO/UNTIL loops and not in FOR/NEXT loops.  In the DO/UNTIL loop you get to control the condition, and it is rather simple to just compare the control variable to zero.  By contrast, for a FOR/NEXT loop IntyBASIC seems to always want to test the control variable to see if it is greater or lesser than the limit, so the generate code would be the same either way.

 

However, do not go replacing FOR/NEXT loops with DO/UNTIL loops!  Because the latter doesn't have a built-in control variable, you will have to do the incrementing or decrementing yourself, which incurs a round-trip to RAM to fetch the value, update it, and then save it -- and this is on top of the additional fetch needed by the test condition to read the control variable.

 

By contrast, the FOR/NEXT reads the control variable once, increments or decrements it, stores it, and then can just use the results from the update to test the exit condition without having to read it again from memory.

 

Tip #3:

When testing flags in a bitfield, it is generally more efficient to mask the bits of interest and compare against zero.  Even better, you should leverage the fact that logical conditions are only false when zero, and true otherwise.

 

This tip is yet another variation on the first one, but it applies specifically to Boolean operations.  As stated above, an IF condition will be true when the value of the expression is anything other than zero.  We can use this to our advantage by expressing our Boolean logic in terms of zero or non-zero values.

 

For example, if your game uses an 8-bit variable as a status register where each bit or group of bits indicate a particular object status or property, then the most efficient way to test these flags is to mask them using the Boolean AND operator.

 

To illustrate, consider the following status flags:

Const OBJ_INACTIVE = &00000000  ' No flags -- object is inactive
Const OBJ_ACTIVE   = &00000001  ' Object is active
Const OBJ_MOTION   = &00000010  ' Object can move
Const OBJ_ANIMATE  = &00000100  ' Object is animated
Const OBJ_STUNNED  = &00001000  ' Object is stunned

 

Our code will use them to indicate that an object is active, in motion, and animated:

' Activate the object fully
ObjStatus = (OBJ_ACTIVE Or OBJ_MOTION Or OBJ_ANIMATE)

 

Now, suppose we only want to move the object when its OBJ_MOTION flag is set.  The most logical way to do this is to mask the flag and test if the result is exactly the value of our flag, like this:

' Test if the motion flag is set
If ((ObjStatus And OBJ_MOTION) = OBJ_MOTION) Then
  Gosub MoveObject
End If

 

The above code will certainly work, but we can do better.  There are two facts at play that we can leverage:

  • First, the AND operator will return the value in the bits of the mask, and turn all all other bits to zero.  Therefore, the result is exactly the value of the masked bits.
  • Second, the IF statement will be true when the result of the expression is different from zero.

Taking these two facts together we can deduce that if our flag of interest is set, then the result will be true (the OBJ_MOTION bit, which is not zero), otherwise the result will be false.

 

In that light, we can optimize our code like this:

' Test if the motion flag is set
If (ObjStatus And OBJ_MOTION) Then
  Gosub MoveObject
End If

 

This code is more efficient because it will induce IntyBASIC to generate code that uses the result of the AND expression as the test condition, whereas the previous version required the result of the expression to be subsequently compared against a constant, and use that output as the test condition.

 

Conversely, if you want to test whether a flag is not set, just apply Tip #1 and test the output against zero:

' Test if the stunned flag is not set
If ((ObjStatus And OBJ_STUNNED) = 0) Then
  Gosub DoAttack
End If

 

Using a test for zero in this way will generate code that is much more efficient than any of the following alternatives -- even though they are all correct and perfectly logical:

' Requires converting the result of the expression into a Boolean value
' and then complementing it.
If Not (ObjStatus And OBJ_STUNNED) Then
  Gosub DoAttack
End If


' Requires an extra comparison against a constant
If ((ObjStatus And OBJ_STUNNED) <> OBJ_STUNNED) Then
  Gosub DoAttack
End If


' The extra cost of both of the above, combined
If (Not (ObjStatus And OBJ_STUNNED) = OBJ_STUNNED) Then
  Gosub DoAttack
End If


' Adds an extra "goto" branch to skip over the empty "truth" block
If (ObjStatus And OBJ_STUNNED) Then
  ' Nothing to do here, ignore ...
Else
  Gosub DoAttack
End If

 

That is it for now.  I hope these tips are useful.

 

     -dZ.

  • Like 1
Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.
Note: Your post will require moderator approval before it will be visible.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...