Quiz of the week: limit a value

Go To Last Post
33 posts / 0 new
Author
Message
#1
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

A very common task was to adjust a value with an encoder:

uint16_t adjust( uint16_t val, int8_t delta )
{
  return val + delta;
}

The encoder gives the changing step (-128 .. 127) to increase or decrease the value.

But there was something missing on this routine:
The value should glue on 0, if you try to decrease further or on 65535, if you increase further.
No wrap around should occur.

In asssembler you can simple check the carry flag, but I want a code saving routine in C (for 8bit CPUs).

Any ideas?

Later I will post my solution.

Peter

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I'll just throw something out that might be more efficient than the obvious code.

  int8_t old_upper = (int8_t) (val >> 8);  // + if near 0, - if near 64k
  val += delta;
  int8_t new_upper = (int8_t) (val >> 8);
  if ((old_upper < 0) && (new_upper >= 0))
    val = 0xFFFF;  // pin at max val
  else if ((old_upper >= 0) && (new_upper < 0))
    val = 0;  // pin at min val
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Oh, I get it, finally.

I have many menu systems that adjust system parameters. They generally have a min and max value for each (or each "type" such as "_3DIGIT") and an increment value. I just usually brute-force it with a "generic" routine somewhat like yours.

However, I rarely have a 64k top. Working with a singed 16-bit value and increments (as yours) guaranteed to be small numbers than it is a simple matter to let it overflow/underflow and always compare to max/min and then pull back to max/min.

Yes, this is one of the cases where the lack of CARRY in C is a drawback. If there are a bunch of these and speed is important, then do inline ASM. My parameter settings aren't repetitive, have unique min/max at least by item type, and the limits need to (often) be fetched from EEPROM. So a few cycles and/or a few words in my adjustment "engine" aren't a killer.

For your use, a straightforward way is a 32-bit union (wasteful because only 24 bits are needed) to simulate carry. Let's see how ugly it gets.

#include 

//
// **************************************************************************
//    32-bit value union for remapping/"generic" data
// **************************************************************************
//
//    Byte order:
//
//    Set    .u32 = 0x12345678;
//
//    Then,
//    .u16[0] = 0x5678;
//    .u16[1] = 0x1234;
//
//    .u8[0] = 0x78;
//    .u8[1] = 0x56;
//    .u8[2] = 0x34;
//    .u8[3] = 0x12;
//

union    longmap
{
unsigned long int        u32;            // 32-bit mapping
unsigned int            u16[2];            // 16-bit mapping
unsigned char            u8[4];            // 8-bit mapping
};

// u16[0] holds the 16-bit unsigned value
union longmap   the_work;

signed char     the_incr;   // -128..127
unsigned int    the_value;  // 16-bit unsigned value

void main(void)
{
    the_value = 1234;           // arbitrary
    the_incr = -123;            // arbitrary
    
    the_work.u32 = the_value;   // zero high word
    the_work.u32 += the_incr;   // apply change
    
    if (the_work.u8[3])
        {
        // underflow -- high byte set (bit 32)
        the_work.u16[0] = 0;
        }
    else if (the_work.u8[2])
        {
        // overflow -- second high byte set (bit 17)
        the_work.u16[0] = 0xffff;
        }
        
    the_value = the_work.u16[0];    // store
    
}
                 	.CSEG
                 _main:
                 ; 0000 0025     the_value = 1234;           // arbitrary
00003d ede2      	LDI  R30,LOW(1234)
00003e e0f4      	LDI  R31,HIGH(1234)
00003f 013f      	MOVW R6,R30
                 ; 0000 0026     the_incr = -123;            // arbitrary
000040 e8e5      	LDI  R30,LOW(133)
000041 2e5e      	MOV  R5,R30
                 ; 0000 0027 
                 ; 0000 0028     the_work.u32 = the_value;   // zero high word
000042 01f3      	MOVW R30,R6
000043 2766      	CLR  R22
000044 2777      	CLR  R23
000045 93e0 0180 	STS  _the_work,R30
000047 93f0 0181 	STS  _the_work+1,R31
000049 9360 0182 	STS  _the_work+2,R22
00004b 9370 0183 	STS  _the_work+3,R23
                 ; 0000 0029     the_work.u32 += the_incr;   // apply change
00004d 2de5      	MOV  R30,R5
00004e 91a0 0180 	LDS  R26,_the_work
000050 91b0 0181 	LDS  R27,_the_work+1
000052 9180 0182 	LDS  R24,_the_work+2
000054 9190 0183 	LDS  R25,_the_work+3
000056 d027      	RCALL __CBD1
000057 d021      	RCALL __ADDD12
000058 93e0 0180 	STS  _the_work,R30
00005a 93f0 0181 	STS  _the_work+1,R31
00005c 9360 0182 	STS  _the_work+2,R22
00005e 9370 0183 	STS  _the_work+3,R23
                 ; 0000 002A 
                 ; 0000 002B     if (the_work.u8[3])
                +
000060 91e0 0183+LDS R30 , _the_work + ( 3 )
                 	__GETB1MN _the_work,3
000062 30e0      	CPI  R30,0
000063 f031      	BREQ _0x3
                 ; 0000 002C         {
                 ; 0000 002D         // underflow -- high byte set (bit 32)
                 ; 0000 002E         the_work.u16[0] = 0;
000064 e0e0      	LDI  R30,LOW(0)
000065 93e0 0180 	STS  _the_work,R30
000067 93e0 0181 	STS  _the_work+1,R30
                 ; 0000 002F         }
                 ; 0000 0030     else if (the_work.u8[2])
000069 c00a      	RJMP _0x4
                 _0x3:
                +
00006a 91e0 0182+LDS R30 , _the_work + ( 2 )
                 	__GETB1MN _the_work,2
00006c 30e0      	CPI  R30,0
00006d f031      	BREQ _0x5
                 ; 0000 0031         {
                 ; 0000 0032         // overflow -- second high byte set (bit 17)
                 ; 0000 0033         the_work.u16[0] = 0xffff;
00006e efef      	LDI  R30,LOW(65535)
00006f efff      	LDI  R31,HIGH(65535)
000070 93e0 0180 	STS  _the_work,R30
000072 93f0 0181 	STS  _the_work+1,R31
                 ; 0000 0034         }
                 ; 0000 0035 
                 ; 0000 0036     the_value = the_work.u16[0];    // store
                 _0x5:
                 _0x4:
                +
000074 9060 0180+LDS R6 , 0 + ( _the_work )
000076 9070 0181+LDS R7 , 0 + ( _the_work ) + 1
                 	__GETWRMN 6,7,0,_the_work
                 ; 0000 0037 
                 ; 0000 0038 }
                 _0x6:
000078 cfff      	RJMP _0x6
                 
                 	.DSEG
                 _the_work:
000180           	.BYTE 0x4
                 
                 	.CSEG
                 
                 	.CSEG
                 __ADDD12:
000079 0fea      	ADD  R30,R26
00007a 1ffb      	ADC  R31,R27
00007b 1f68      	ADC  R22,R24
00007c 1f79      	ADC  R23,R25
00007d 9508      	RET
                 
                 __CBD1:
00007e 2ffe      	MOV  R31,R30
00007f 0fff      	ADD  R31,R31
000080 0bff      	SBC  R31,R31
000081 2f6f      	MOV  R22,R31
000082 2f7f      	MOV  R23,R31
000083 9508      	RET
                 

Unfortunately, my compiler does not let me coerce it into holding 32-bit values into register variables. (If I really needed to, I could force the 16-bit pieces to adjacent register pairs to create my own "de facto" union and use casts for the 32-bit operations. If it turns into a "contest"...)

I'll be interested to see your solution.

Lee

You can put lipstick on a pig, but it is still a pig.

I've never met a pig I didn't like, as long as you have some salt and pepper.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

The other straightforward way would be to check for +/- increment first, and have two code paths, and check the magnitude before the add/subtract. That would have more words, probably, but the cycle count should be low.

#include 
void main(void)
{
signed char     the_incr;   // -128..127
unsigned char   frog;       // working 8-bit
unsigned int    the_value;  // 16-bit unsigned value

    the_value = 1234;           // arbitrary
    the_incr = -123;            // arbitrary

    if (the_incr < 0)
        {
        // subtracting (this is the easy one)
        frog = -the_incr;
        if (frog > the_value)
            {
            the_value = 0;
            }
        else
            {
            the_value -= frog;
            }
        }
    else
        {
        // adding--this is harder
        
        // with the small increment value, overflow can only occur when
        // the high bit is already set, and then that bit will become reset
        // if overflow.
        
        // I'll use an "if" for this test but it could also be done 
        // with a register copy of the original value.
        if (the_value & 0x8000)
            {
            the_value += the_incr;
            if (!(the_value & 0x8000))
                {
                // overflow
                the_value = 0xffff;
                }
                
            }
        else
            {
            the_value += the_incr;
            }
        }    
}
                 	.CSEG
                 _main:
                 ; 0000 0007 signed char     the_incr;   // -128..127
                 ; 0000 0008 unsigned char   frog;       // working 8-bit
                 ; 0000 0009 unsigned int    the_value;  // 16-bit unsigned value
                 ; 0000 000A 
                 ; 0000 000B     the_value = 1234;           // arbitrary
                 ;	the_incr -> R17
                 ;	frog -> R16
                 ;	the_value -> R18,R19
                +
00003d ed22     +LDI R18 , LOW ( 1234 )
00003e e034     +LDI R19 , HIGH ( 1234 )
                 	__GETWRN 18,19,1234
                 ; 0000 000C     the_incr = -123;            // arbitrary
00003f e815      	LDI  R17,LOW(133)
                 ; 0000 000D 
                 ; 0000 000E     if (the_incr < 0)
000040 3010      	CPI  R17,0
000041 f49c      	BRGE _0x3
                 ; 0000 000F         {
                 ; 0000 0010         // subtracting (this is the easy one)
                 ; 0000 0011         frog = -the_incr;
000042 2fe1      	MOV  R30,R17
000043 95e1      	NEG  R30
000044 2f0e      	MOV  R16,R30
                 ; 0000 0012         if (frog > the_value)
000045 01f9      	MOVW R30,R18
000046 2fa0      	MOV  R26,R16
000047 e0b0      	LDI  R27,0
000048 17ea      	CP   R30,R26
000049 07fb      	CPC  R31,R27
00004a f418      	BRSH _0x4
                 ; 0000 0013             {
                 ; 0000 0014             the_value = 0;
                +
00004b e020     +LDI R18 , LOW ( 0 )
00004c e030     +LDI R19 , HIGH ( 0 )
                 	__GETWRN 18,19,0
                 ; 0000 0015             }
                 ; 0000 0016         else
00004d c006      	RJMP _0x5
                 _0x4:
                 ; 0000 0017             {
                 ; 0000 0018             the_value -= frog;
00004e 2fe0      	MOV  R30,R16
00004f 01d9      	MOVW R26,R18
000050 e0f0      	LDI  R31,0
000051 1bae      	SUB  R26,R30
000052 0bbf      	SBC  R27,R31
000053 019d      	MOVW R18,R26
                 ; 0000 0019             }
                 _0x5:
                 ; 0000 001A         }
                 ; 0000 001B     else
000054 c013      	RJMP _0x6
                 _0x3:
                 ; 0000 001C         {
                 ; 0000 001D         // adding--this is harder
                 ; 0000 001E 
                 ; 0000 001F         // with the small increment value, overflow can only occur when
                 ; 0000 0020         // the high bit is already set, and then that bit will become reset
                 ; 0000 0021         // if overflow.
                 ; 0000 0022 
                 ; 0000 0023         // I'll use an "if" for this test but it could also be done
                 ; 0000 0024         // with a register copy of the original value.
                 ; 0000 0025         if (the_value & 0x8000)
000055 ff37      	SBRS R19,7
000056 c00b      	RJMP _0x7
                 ; 0000 0026             {
                 ; 0000 0027             the_value += the_incr;
000057 2fe1      	MOV  R30,R17
000058 e0f0      	LDI  R31,0
000059 fde7      	SBRC R30,7
00005a efff      	SER  R31
                +
00005b 0f2e     +ADD R18 , R30
00005c 1f3f     +ADC R19 , R31
                 	__ADDWRR 18,19,30,31
                 ; 0000 0028             if (!(the_value & 0x8000))
00005d fd37      	SBRC R19,7
00005e c002      	RJMP _0x8
                 ; 0000 0029                 {
                 ; 0000 002A                 // overflow
                 ; 0000 002B                 the_value = 0xffff;
                +
00005f ef2f     +LDI R18 , LOW ( - 1 )
000060 ef3f     +LDI R19 , HIGH ( - 1 )
                 	__GETWRN 18,19,-1
                 ; 0000 002C                 }
                 ; 0000 002D 
                 ; 0000 002E             }
                 _0x8:
                 ; 0000 002F         else
000061 c006      	RJMP _0x9
                 _0x7:
                 ; 0000 0030             {
                 ; 0000 0031             the_value += the_incr;
000062 2fe1      	MOV  R30,R17
000063 e0f0      	LDI  R31,0
000064 fde7      	SBRC R30,7
000065 efff      	SER  R31
                +
000066 0f2e     +ADD R18 , R30
000067 1f3f     +ADC R19 , R31
                 	__ADDWRR 18,19,30,31
                 ; 0000 0032             }
                 _0x9:
                 ; 0000 0033         }
                 _0x6:
                 ; 0000 0034 }
                 _0xA:
000068 cfff      	RJMP _0xA

With the copy register it becomes nearly as mentioned above

#include 
void main(void)
{
signed char     the_incr;   // -128..127
unsigned int    the_value;  // 16-bit unsigned value
unsigned int    the_copy;   // a copy of the_value

    the_value = 1234;           // arbitrary
    the_incr = -123;            // arbitrary

    the_copy = the_value;       // to save a few words, only high 8 bits are needed
    
    the_value += the_incr;
    
    // Underflow check
    if ((!(the_copy & 0x8000)) && (the_value & 0x8000))
        {
        the_value = 0;
        }
    else if ((the_copy & 0x8000) && (!(the_value & 0x8000)))
        {
        // Overflow
        the_value = 0xffff;
        }
}
                 	.CSEG
                 _main:
                 ; 0000 0004 signed char     the_incr;   // -128..127
                 ; 0000 0005 unsigned int    the_value;  // 16-bit unsigned value
                 ; 0000 0006 unsigned int    the_copy;   // a copy of the_value
                 ; 0000 0007 
                 ; 0000 0008     the_value = 1234;           // arbitrary
                 ;	the_incr -> R17
                 ;	the_value -> R18,R19
                 ;	the_copy -> R20,R21
                +
00003d ed22     +LDI R18 , LOW ( 1234 )
00003e e034     +LDI R19 , HIGH ( 1234 )
                 	__GETWRN 18,19,1234
                 ; 0000 0009     the_incr = -123;            // arbitrary
00003f e815      	LDI  R17,LOW(133)
                 ; 0000 000A 
                 ; 0000 000B     the_copy = the_value;       // to save a few words, only high 8 bits are needed
000040 01a9      	MOVW R20,R18
                 ; 0000 000C 
                 ; 0000 000D     the_value += the_incr;
000041 2fe1      	MOV  R30,R17
000042 e0f0      	LDI  R31,0
000043 fde7      	SBRC R30,7
000044 efff      	SER  R31
                +
000045 0f2e     +ADD R18 , R30
000046 1f3f     +ADC R19 , R31
                 	__ADDWRR 18,19,30,31
                 ; 0000 000E 
                 ; 0000 000F     // Underflow check
                 ; 0000 0010     if ((!(the_copy & 0x8000)) && (the_value & 0x8000))
000047 fd57      	SBRC R21,7
000048 c002      	RJMP _0x4
000049 fd37      	SBRC R19,7
00004a c001      	RJMP _0x5
                 _0x4:
00004b c003      	RJMP _0x3
                 _0x5:
                 ; 0000 0011         {
                 ; 0000 0012         the_value = 0;
                +
00004c e020     +LDI R18 , LOW ( 0 )
00004d e030     +LDI R19 , HIGH ( 0 )
                 	__GETWRN 18,19,0
                 ; 0000 0013         }
                 ; 0000 0014     else if ((the_copy & 0x8000) && (!(the_value & 0x8000)))
00004e c007      	RJMP _0x6
                 _0x3:
00004f ff57      	SBRS R21,7
000050 c002      	RJMP _0x8
000051 ff37      	SBRS R19,7
000052 c001      	RJMP _0x9
                 _0x8:
000053 c002      	RJMP _0x7
                 _0x9:
                 ; 0000 0015         {
                 ; 0000 0016         // Overflow
                 ; 0000 0017         the_value = 0xffff;
                +
000054 ef2f     +LDI R18 , LOW ( - 1 )
000055 ef3f     +LDI R19 , HIGH ( - 1 )
                 	__GETWRN 18,19,-1
                 ; 0000 0018         }
                 ; 0000 0019 }
                 _0x7:
                 _0x6:
                 _0xA:
000056 cfff      	RJMP _0xA

A "bit" variable could be used instead of the register copy but it doesn't save cycles or code words. It would, however, release a pair of registers that hold the copy.

Lee

You can put lipstick on a pig, but it is still a pig.

I've never met a pig I didn't like, as long as you have some salt and pepper.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Quote:
The other straightforward way would be to check for +/- increment first, and have two code paths, and check the magnitude before the add/subtract.

This is along the lines of the way I'd do it. Once the sign of delta is known, go ahead and add/subtract it. If the result got bigger on a subtract, or smaller on an add, you crossed the limit.

old = orig_value
new = orig_value + delta
if old > new
  if delta < 0, error
else
  if delta > 0, error
end if

Chuck Baird

"I wish I were dumber so I could be more certain about my opinions. It looks fun." -- Scott Adams

http://www.cbaird.org

Last Edited: Tue. Oct 27, 2009 - 07:10 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

How about

uint16_t adjust( uint16_t val, int8_t delta )
{
uint16_t tval=val+delta;
if (delta>0) {
  if (tvalval) tval=0;
}
  return tval;
}
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Quote:

How about
Code:

uint16_t adjust( uint16_t val, int8_t delta )
{
uint16_t tval=val+delta;
if (delta>0) {
if (tval } else {
if (tval>val) tval=0;
}
return tval;
}


That is basically what I have above, with the_copy. However, I "know" that I have coerced the compiler to keep the_copy in a register, and I "know" that my check of the high bit will result in a check of that bit--an SBRS/SBRC as you can see. With your full 16-bit comparison, a full sequence will be done followed by the branch.

(Unfortunately, my compiler apparently wants to exercise the RJMP instruction to extremes...)

Lee

You can put lipstick on a pig, but it is still a pig.

I've never met a pig I didn't like, as long as you have some salt and pepper.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

The straight forward approach.

uint16_t adjust( uint16_t val, int8_t delta )
{
  uint16_t res;

  res =  val + delta;

  if(delta < 0) {
    if(res > val) return 0;
  } else {
    if(res < val) return 65535;
  }
  return res;
}

The slightly less straight forward approach.

typedef union bwd_u {
    uint32_t val32;
    uint16_t val16[2];
    uint8_t  val8[4];
} bwd_t;

uint16_t adjust( uint16_t val, int8_t delta )
{
  bwd_t res; // we only need 24 bits, but there is no 24bit type
  
  res.val32 = val + delta;
  
  // carry = val8[2]
  // carry will be 1 if overflowed from addition
  // carry will be 255 if overflowed from subtraction  
  // carry will be 0 if no overflow happened
  if(res.val8[2]) {
      if(res.val8[2]==1) return 65535;
      return 0;
  }
  return res.val16[0];
}

[edit] got interrupted while posting, seems all this was covered off already.

Here is the "portable" version of the less straight forward version

uint16_t adjust( uint16_t val, int8_t delta )
{
  uint32_t res; // we only need 24 bits, but there is no 24bit type
  uint8_t carry;

  res = val + delta;
  carry = res >> 16;

  // carry will be 1 if overflowed from addition
  // carry will be 255 if overflowed from subtraction 
  // carry will be 0 if no overflow happened
  if(carry) {
      if(carry==1) return 65535;
      return 0;
  }
  return res;
} 

Writing code is like having sex.... make one little mistake, and you're supporting it for life.

Last Edited: Tue. Oct 27, 2009 - 07:46 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Quote:

[edit] got interrupted while posting, seems all this was covered off already.


LOL--your union solution appears to be nearly identical to mine?!? Great minds think alike.

I don't know what the "judging criteria" for the contest are. If it is number of cycles, then if the function approach is used it will depend on parameter/result passing conventions of the compiler used. If it is words then my "checking the high bit" should be smaller than comparing the previous and new values.

Peter is clever; let's see his "solution"...

You can put lipstick on a pig, but it is still a pig.

I've never met a pig I didn't like, as long as you have some salt and pepper.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

//high side overflow
if(~value < delta){value=0xFFFF;}

//low side overflow
if(value < -delta){value=0;}

high side explained:
the complement is the remainder left, if the remainder is smaller than delta, an overflow occurs
if delta is negative, the remainder is always bigger so no overflow

low side:
if the value is smaller than delta * -1,
then the remainder to be subtracted, the value itself, is also smaller than the substraction, delta*-1, so overflow occurs.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

well I can think of a couple of more ways to do it, and avoid the 32bit maths, but I'm not sure it'll be any quicker due to the additional calculations.

Writing code is like having sex.... make one little mistake, and you're supporting it for life.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

johnnyboy wrote:
//high side overflow
if(~value < delta){value=0xFFFF;}

//low side overflow
if(value < -delta){value=0;}

high side explained:
the complement is the remainder left, if the remainder is smaller than delta, an overflow occurs
if delta is negative, the remainder is always bigger so no overflow

low side:
if the value is smaller than delta * -1,
then the remainder to be subtracted, the value itself, is also smaller than the substraction, delta*-1, so overflow occurs.

In theory that works, problem is that you'll be comparing signed and unsigned values, which means your compares alone will overflow. To work your compares will need to be done as 32bit signed values.

Now with a slight edit, it can be made to work in the 16bit unsigned domain. [by constraining the checks to only when they are relevant]

uint16_t adjust( uint16_t val, int8_t delta )
{
  if(delta & 0x80) { // delta is negative
    //low side overflow
    if(val < -delta) return 0; 
  } else { // delta is positive 
    //high side overflow
    if((~val) < delta) return 65535;
  }
  return val + delta;

This is still not likely to be as efficient as some of the other options, due to the fact that there is still a 16bit compare required.

Writing code is like having sex.... make one little mistake, and you're supporting it for life.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Heh I have actually had the pleasure of simulating a quadrature encoder with an AVR and some capacitive wheel.

The capacitive wheel gave a 7-bit angle, so basically one had to know that when angle wrapped around for example from 127 to 42, it really meant 43 pulses in the positive direction - basically the idea is similar here. It seems that the increment is accumulated (perhaps in an interrupt) until processed in main loop.

Here is mine solution to this. Something similar already seen before, more efficient even. But you could set the limits to something else than 65535 and 0, and it should work, as it does not rely on 16-bit wraparound.

uint16_t adjust( uint16_t val, int8_t delta )
{
    if (delta>0)
    {
        // positive delta
        // is value less than biggest value you can add delta to?
        if (val<(65535-delta)) return val+delta; // yes, can add
        return 65535; // no, cannot add, limit it
    }
    else 
    {
        //negative delta, or 0
        // if value is more than -delta, can safely subtract
        if (value>(0-delta)) return value+delta;
        return 0; //value is less than decrement, limit it
    }
} 
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

My code works in this way:
If you add two positive numbers and the sum was below one operand, then an overflow occurs.
But if the sum was above the negative operand, seen as unsigned positive, then an underflow occurs.

It use the c conversion rule, that comparison of a signed and a unsigned value was done with both seen as unsigned.

uint16_t adjust( uint16_t val, int8_t delta8 )  // 36 byte
{
  int16_t delta = delta8;

  val += delta;
  if( val < delta ){
    if( delta >= 0 )
      val = 65535;
  }else{
    if( delta < 0 )
      val = 0;
  }
  return val;
}

ad the generated assembler:

uint16_t adjust( uint16_t val, int8_t delta8 )  // 36 byte
{
  int16_t delta = delta8;
  6c:   77 27           eor     r23, r23
  6e:   67 fd           sbrc    r22, 7
  70:   70 95           com     r23

  val += delta;
  72:   86 0f           add     r24, r22
  74:   97 1f           adc     r25, r23
  if( val < delta ){
  76:   86 17           cp      r24, r22
  78:   97 07           cpc     r25, r23
  7a:   28 f4           brcc    .+10            ; 0x86 
    if( delta >= 0 )
  7c:   77 fd           sbrc    r23, 7
  7e:   07 c0           rjmp    .+14            ; 0x8e 
  80:   8f ef           ldi     r24, 0xFF       ; 255
  82:   9f ef           ldi     r25, 0xFF       ; 255
  84:   08 95           ret
      val = 65535;
  }else{
    if( delta < 0 )
  86:   77 ff           sbrs    r23, 7
  88:   02 c0           rjmp    .+4             ; 0x8e 
  8a:   80 e0           ldi     r24, 0x00       ; 0
  8c:   90 e0           ldi     r25, 0x00       ; 0
      val = 0;
  }
  return val;
}
  8e:   08 95           ret

Peter

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

kk6gm wrote:
I'll just throw something out that might be more efficient than the obvious code.

Your code looks very impressive.
It generate tight code without any useless MOV instruction. :!:
Are you the writer of the AVR-GCC. :?:

I have often tons of useless MOV instructions generated.
Many of these are removed by the optimization switch:
"-fno-split-wide-types".
But with this switch your code does the opposite, it insert useless MOVs. :shock:

With "-fno-split-wide-types"
Your code: 44 byte
My code: 36 byte

Without "-fno-split-wide-types"
Your code: 36 byte
My code: 40 byte

Peter

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Peter, Nice solution.

I'd add the cast to uint16_t in the if, just to be explicate and make the code more clear to the reader. Also in the first case, it is impossible for delta to be equal to 0. (because val can never be less than 0 because it is unsigned) As such a test for greater than is sufficient. [edit, never mind that last bit, by adding the equal condition it allows SBRC to be used to test for a positive value - nice optimization!]

uint16_t adjust( uint16_t val, int8_t delta8 )  // 36 byte
{
  int16_t delta = delta8;

  val += delta;
  if( val < (uint16_t)delta ){
    if( delta > 0 )
      val = 65535;
  } else {
    if( delta < 0 )
      val = 0;
  }
  return val;
}

Not sure how this would fare but here is another implementation

uint16_t adjust( uint16_t val, int8_t delta )
{
  uint8_t s15, r15;
  
  s15 = (uint8_t)(val >> 8);
  r15 = s15;
  val  += delta;  
  s15 ^= delta;
  r15 ^= (uint8_t)(val >> 8);
  s15 &= r15;

  if(s15 & 0x80) {
      if(delta & 0x80) val = 0;
      else val = 65535;
  }
  return val;
}

Writing code is like having sex.... make one little mistake, and you're supporting it for life.

Last Edited: Wed. Oct 28, 2009 - 12:53 AM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

glitch wrote:
... code ...

Variation to your code (note that upper byte of val increments/decrements or won't change, so the only time old/new combines 0 and FF in any order is if it over/underflows) (I am lazy and just borrowed your code so the temporaries' names now make no sense, sorry).

uint16_t adjust( uint16_t val, int8_t delta ) {
  uint8_t s15, r15;
  
  s15 = (uint8_t)(val >> 8);
  val  += delta;  
  r15 = (uint8_t)(val >> 8);

  if ((s15 ^ r15) == 0xFF) {
    val = s15 | ((uint16_t) s15 << 8)
  }
  return val;
}

But I am afraid it will choke on the promotions in a less-than-perfectly-optimising compiler, anyway this is maybe roughly what I'd attempt to do in asm.

For the record: I dislike any attempt to over-optimise C.

I remember the thrill of reading Peter's assembly routines; pity he fell for C. And I'd like to see this very routine being super-optimised in asm.

JW

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

nice. I missed that the overflow will affect the whole byte in this case, due to the range of delta.

Re-arranging a bit, to give the optimizer more of a chance. (I think) [comments represent guessed opcode result]

uint16_t adjust( uint16_t val, int8_t delta ) {
  uint8_t overflow;
 
  overflow = (uint8_t)(val >> 8);                // mov
  val  += delta;                                 // eor,sbrc,com,add,adc
  overflow ^= (uint8_t)(val >> 8);               // eor

  if (overflow == (uint8_t)0xff) {               // cpi,brne
    overflow ^= (uint8_t)(val >> 8);             // eor
    val = overflow | ((uint16_t) overflow << 8); // mov,mov
  }
  return val;
} 

Writing code is like having sex.... make one little mistake, and you're supporting it for life.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

glitch wrote:

    val = overflow | ((uint16_t) overflow << 8); // mov,mov
} 


Tried quickly with gcc both 4.2 and 4.3; and, as I said above, this chokes on gcc's idea of integer promotions and conversions (overflow is initially in r25):

                          mov r24,r25
  66 004a 90E0      		ldi r25,lo8(0)
  67 004c 782F      		mov r23,r24
  68 004e 6627      		clr r22
  69 0050 682B      		or r22,r24
  70 0052 792B      		or r23,r25

This is the reason why I don't like these "let's optimise C" games - the outcome depends too much on the given optimiser's state of mind.

Let's just quiz now on the same thing in inline asm... ;-)

JW

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Quote:

This is the reason why I don't like these "let's optimise C" games - the outcome depends too much on the given optimiser's state of mind.

Once you "know" from experience/study the "mindset" of the compiler, you can usually predict the code sequence. A look at the output and you say "that part looks ugly". Upon examination, you find that you didn't give the compiler a chance as has been mentioned several times--a well-placed cast may do wonders.

Now, wek, you may write the optimal ASM sequence the first time. If you are one of those wizards that think in opcodes then I can't match you no matter what the language. I've known a handful of those people in my life.

But the average ASM programmer ain't gonna get the "best" sequence for a particular piece of code the first time. The steps are roughly the same: "that part looks ugly" followed by trials on how to make it better.

Lee

You can put lipstick on a pig, but it is still a pig.

I've never met a pig I didn't like, as long as you have some salt and pepper.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

wek wrote:
glitch wrote:

    val = overflow | ((uint16_t) overflow << 8); // mov,mov
} 


Tried quickly with gcc both 4.2 and 4.3; and, as I said above, this chokes on gcc's idea of integer promotions and conversions (overflow is initially in r25):

                          mov r24,r25
  66 004a 90E0      		ldi r25,lo8(0)
  67 004c 782F      		mov r23,r24
  68 004e 6627      		clr r22
  69 0050 682B      		or r22,r24
  70 0052 792B      		or r23,r25

I see, well then a slightly less optimal, but should still do better than what is happening above is:

    val = (int16_t)((int8_t)overflow); //mov,clr,sbrc,ser

Another fun variation, be interesting to see how the compiler chews on this:

    val = overflow * 0x0101; 

Though I can't help but think there has to be a way to construct the original statement so that it does not choke, given the presented results earlier in this thread.

Writing code is like having sex.... make one little mistake, and you're supporting it for life.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

theusch wrote:
Now, wek, you may write the optimal ASM sequence the first time. If you are one of those wizards that think in opcodes then I can't match you no matter what the language.

There is no wizardry to see that val = overflow | ((uint16_t) overflow << 8); converts to two movs. In fact, this C line is just a poor attempt to write down the two movs using the limited choice of expressions the C language offers (you, the C wizard, will certainly come up with a better one).

But, Lee, you know that there's only one honorable way to settle this dispute: at dawn or dusk, just behind the city walls, you and me and the seconds, your shot first... ;-)

---
Out of curiosity, you seem to use a non-gcc compiler, could you please try the above short function, how does that one cope with it? Thanks.

Jan

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

glitch wrote:

I see, well then a slightly less optimal, but should still do better than what is happening above is:

    val = (int16_t)((int8_t)overflow); //mov,clr,sbrc,ser


I am reluctant to cast uint_Nt into int_Nt - as per standard, the behaviour is undefined and warning ought be thrown.

glitch wrote:

Another fun variation, be interesting to see how the compiler chews on this:

    val = overflow * 0x0101; 


Bleah. ;-)

Keep in mind, that Peter's original task was to write it "for an 8-bit microcontroller", not specifying compiler nor mcu. A less-mature and less-optimising compiler might easily cough to death on a multiply like that...

glitch wrote:
Though I can't help but think there has to be a way to construct the original statement so that it does not choke, given the presented results earlier in this thread.
Yes, sure. This is the very reason why inline assembler was invented ;-)

---
Just out of curiosity, I've thrown the same into SDCC. The above snippet ended up in the very same way (overflow was in r4:

                            314 ;	z.c:48: val = overflow | ((uint16_t) overflow << 8); // mov,mov
   00ED 7D 00               315 	mov	r5,#0x00
   00EF 8C 07               316 	mov	ar7,r4
   00F1 E4                  317 	clr	a
   00F2 FE                  318 	mov	r6,a
   00F3 4C                  319 	orl	a,r4
   00F4 FA                  320 	mov	r2,a
   00F5 EF                  321 	mov	a,r7
   00F6 4D                  322 	orl	a,r5
   00F7 FB                  323 	mov	r3,a

JW

Attachment(s): 

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I wrote:
glitch wrote:

I see, well then a slightly less optimal, but should still do better than what is happening above is:

    val = (int16_t)((int8_t)overflow); //mov,clr,sbrc,ser


I am reluctant to cast uint_Nt into int_Nt - as per standard, the behaviour is undefined and warning ought be thrown.

Tried.

 137 00a6 692F      		mov r22,r25
 138 00a8 7727      		clr r23
 139 00aa 67FD      		sbrc r22,7
 140 00ac 7095      		com r23

As expected, better; reluctance remains.

I wrote:

glitch wrote:

Another fun variation, be interesting to see how the compiler chews on this:

    val = overflow * 0x0101; 


Bleah. ;-)

Keep in mind, that Peter's original task was to write it "for an 8-bit microcontroller", not specifying compiler nor mcu. A less-mature and less-optimising compiler might easily cough to death on a multiply like that...


Even the mature one ;-) could not resist to go for the multiplication:

 144 00b6 30E0      		ldi r19,lo8(0)
 145 00b8 81E0      		ldi r24,lo8(257)
 146 00ba 91E0      		ldi r25,hi8(257)
 147 00bc 289F      		mul r18,r24
 148 00be B001      		movw r22,r0
 149 00c0 299F      		mul r18,r25
 150 00c2 700D      		add r23,r0
 151 00c4 389F      		mul r19,r24
 152 00c6 700D      		add r23,r0
 153 00c8 1124      		clr r1

JW

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

yeah I didn't expect the multiply to fare well, but sometimes a compiler will surprise you with an optimization.

I'm not sure the casting of an unsigned to a signed value is "undefined". An explicate cast is a deliberate change in behavior and should not generate a warning. An implicate cast, on the other hand, could generate a warning when the data is switching signedness. [I'd love it if you could point me to the clause where it states that this is undefined]

Writing code is like having sex.... make one little mistake, and you're supporting it for life.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

glitch wrote:
[I'd love it if you could point me to the clause where it states that this is undefined]

6.3.1.3 Signed and unsigned integers wrote:
3 Otherwise, the new type is signed and the value cannot be represented in it; either the result is implementation-defined or an implementation-defined signal is raised.

So, I was wrong: it is not undefined but implementation-defined. At the end of the day, it is still not the absolutely-right-thing-to-do, even if the Derek Jones book in the related chapter has to say this:
The New C Standard wrote:
The usual behavior is for the appropriate number of least significant bits
from the original value to be treated as the converted value. The most significant bit of this new value is treated as a sign bit, which is sign-extended to fill the available space if the value is being held in a register.
If the conversion occurs immediately before a store (i.e., a right-hand side value is converted before being assigned into the left hand side object), there is often no conversion; the appropriate number of value bits are simply written into storage

which is of course what one would "naively" expect.

At the same time, Jones warns, that "some older processors" [the endnote points to VAX11] did actually throw a signal in similar situation.

JW

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Quote:

[I'd love it if you could point me to the clause where it states that this is undefined]

So would I. I searched for every "cast" in the draft that I use and found no mention of "undefined" exceptions, the one discussed here or others.

You can put lipstick on a pig, but it is still a pig.

I've never met a pig I didn't like, as long as you have some salt and pepper.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

theusch wrote:
Quote:

[I'd love it if you could point me to the clause where it states that this is undefined]

So would I. I searched for every "cast" in the draft that I use and found no mention of "undefined" exceptions, the one discussed here or others.

6.5.4 Cast operators wrote:
4 Preceding an expression by a parenthesized type name converts the value of the expression to the named type. This construction is called a cast.emphasize JW

Thus, cast constitutes a conversion. For rules of conversion, see 6.3, of which I quoted the relevant verse above.

I repeat, my fault, it is NOT undefined, the behaviour of uintN_t -to- intN_t cast is implementation-defined.

JW

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Thanks for pointing out the relevant clause.

In practice I have not had any issue when explicitly casting between signed & unsigned values. It only ever seems to alter how the value is interpreted, and not alter the actual binary representation, if the two types have the same rank. I will certainly have to pay closer attention to that in the future.

Writing code is like having sex.... make one little mistake, and you're supporting it for life.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Quote:

Thus, cast constitutes a conversion. For rules of conversion, see 6.3, of which I quoted the relevant verse above.

Yahbut, 6.3[.0.]2 says there is no change in value, right? Just "relabeling".

[standards wording makes my head hurt]

Quote:

I repeat, my fault, it is NOT undefined, the behaviour of uintN_t -to- intN_t cast is implementation-defined.

Be easier on yourself. In either case it is indeed an "exception" that needs to be considered.

That said, we all are trying to get a job done using a cheap/small/limited-resource 8-bit microcontroller. "Get'er done." If I have a critical sequence that I can coerce my compiler to use overlaid register variables as a "hardware union", then I'm going to do it. With your toolchain, other seuences may be better as demonstrated in the code fragments above.

As a cast doesn't change the value I don't see anything undefined or implementation-defined about it in this case. Warning or not--that is up to your religious and political views.

You can put lipstick on a pig, but it is still a pig.

I've never met a pig I didn't like, as long as you have some salt and pepper.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Thank you for the lively discussion. :D

It seems, my solution was not so bad.

I'm also thinking, that I would add acceleration to the encoder, which may cause steps above the 8 bit range.
In this case my code would work also.

Peter

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Just realized that my method fails when crossing from 0x7Fxx to 0x80xx.... going to find some quiet place to practice more self-punishment... :-(((

JW

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

lol, I missed it too. Though I have to admit something was bothering me in the back of my head, just never put my finger on it, or thought about it too much. So I guess it's back to the pre-modified version ;)

Writing code is like having sex.... make one little mistake, and you're supporting it for life.