Sign Extending 10-bit signed value?

Go To Last Post
120 posts / 0 new

Pages

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

Compare the "politically correct" bitfield solution with the simple sequence originally proposed by us pagans:

https://www.avrfreaks.net/comment...

	result = ADCW;
  46:	80 91 78 00 	lds	r24, 0x0078
  4a:	90 91 79 00 	lds	r25, 0x0079
	if (result & 0x0200) result |= 0xfc00;
  4e:	91 fd       	sbrc	r25, 1
  50:	9c 6f       	ori	r25, 0xFC	; 252
	PORTD = result;
  52:	8b b9       	out	0x0b, r24	; 11
	PORTD = result>>8;
  54:	89 2f       	mov	r24, r25
...

Same SBRC/ORI in both CodeVision and GCC.

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.

Last Edited: Fri. Oct 24, 2014 - 07:55 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

A re-read of the thread was "interesting".  ;)

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

I didn't read all 11 pages of this thread, only the first couple. Here's a portable branch-free approach:

int n = <10-bit input>;
n = (n ^ 0x200) - 0x200;

This converts it to offset-binary, then subtracts the zero bias. It is completely portable (to satisfy purists here) and works regardless of how wide an int is (it'll of course work for int16_t, int32_t, or whatever). It should be just as efficient for AVR, since both instructions don't touch the lower byte.

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

Cool solution. Edit: Seems like GCC (also avr-gcc) optimize my solution and this solution to to same 3 assembler instructions AVR, or 2 instructions on an IA64.

Last Edited: Sat. Nov 1, 2014 - 08:18 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Indeed.  Thank you @christop!  This is now and forever in my toolbox.

 

A neat link to other 'bit twiddling' hacks, too...

"Experience is what enables you to recognise a mistake the second time you make it."

"Good judgement comes from experience.  Experience comes from bad judgement."

"Wisdom is always wont to arrive late, and to be a little approximate on first possession."

"When you hear hoofbeats, think horses, not unicorns."

"Fast.  Cheap.  Good.  Pick two."

"We see a lot of arses on handlebars around here." - [J Ekdahl]

 

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

Have to make such binary operations always clear by examples:

 

10-bit signed number is b000000ji hgfedcba

Zero or positive number has j=0, negative number has j=1.

Example for zero or positive number:
value >= 0     b0000000i hgfedcba
constant 0x200 b00000010 00000000
XOR result     b0000001i hgfedcba
constant 0x200 b00000010 00000000
minus result   b0000000i hgfedcba

Example for negative number:
value < 0      b0000001i hgfedcba
constant 0x200 b00000010 00000000
XOR result     b0000000i hgfedcba
constant 0x200 b00000010 00000000
minus result   b1111111i hgfedcba

 

Yea, seems to work great!

In the beginning was the Word, and the Word was with God, and the Word was God.

Last Edited: Sun. Nov 2, 2014 - 08:44 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

This has been really interesting, folks.

 

Not being steeped in the mysteries of signed binary arithmetic, it has been a great learning event. Appreciate everyone's input.

 

Jim

Jim Wagner Oregon Research Electronics, Consulting Div. Tangent, OR, USA http://www.orelectronics.net

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

So here is an additional bonus weed end problem for you all. Find the optimal  solution to compute the average of 10 consecutive samples of the 10 bit signed numbers and give the result as a 16 bit signed number.
 

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

It is not clear, which average you mean, for example

- block average,

- moving average,

- average, where the newer values count more than the older

=> FIR or IIR filter.

So, instead of solving the "weed end" problem wink, I would start with the week end problem first:

compute the moving average of 64 consecutive samples of 10 bit signed numbers and give the result as a 16 bit signed number.

Samples of 511 should lead to 32702,

samples of -512 should lead to 32768.

In the beginning was the Word, and the Word was with God, and the Word was God.

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

By average I ment arithmetic mean.  Of course input data should allow arbitrary values just as if the input is a bit noisy real time AD-converted signal.  Would it be best to convert to the 16-bit signed format first before adding a new number or is it possible to have some other solution that also performs better? For myself I guess rehab is the best solution.
 

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

Neither problem is terribly difficult.

For the first, the hard part is deciding how to divide by ten.

Should one be fussy about rounding?

For the second, the main problem is storage.

One will have to store 64 samples.

That is 80 or 128 bytes.

If one has the resources, the problem is not hard.

For such things, I'm more likely to use a decaying average.

Iluvatar is the better part of Valar.

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

A simple moving average (SMA) and weighted moving average would need to store a window's worth of samples but an exponential moving average (EMA) requires only the previous sample. I imagine that's what skeeve is referring to by "decaying average".

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

Correct.

Iluvatar is the better part of Valar.

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

Often a decaying average is enough. But if you do not want to have any historical data after a given number of sampls, the simple moving average is better suited:

 

#define FILTER_SIZE 64
/* Simple Moving Average filter:
   inData is assumed to be in the range of [-512; 511] (= 10bit, sign extended);
   the return value is scaled by the factor FILTER_SIZE=64 related to the input data */   
int16_t filterSMA(int16_t inData)
{
    static int16_t buffer[FILTER_SIZE];
    static int16_t average;
    static uint16_t bufferIndex;
    static uint8_t startCounter;

    /* add the latest value to the average */
    average += inData;
    /* remove oldest value from the average */
    average -= buffer[bufferIndex];    
    
    /* store to buffer */
    buffer[bufferIndex] = inData;
    bufferIndex++;
    if (bufferIndex>=FILTER_SIZE)
    {
        bufferIndex = 0;
    }
    
    if (startCounter<FILTER_SIZE)
    {   /* special handling, if buffer is not completely filled (not settled) */
        startCounter++;
        return average*FILTER_SIZE/startCounter;
    }
    else
    {
        /* buffer is filled, filter is settled */
        return average;
    }
}

 

A decaying filter would look like this:

 

#define FILTER_STRENGTH        16
/* Decaying filter:
   inData is assumed to be in the range of [-512; 511] (= 10bit, sign extended);
   the return value is scaled by the factor FILTER_SIZE=64 related to the input data;
   Watch out for remaining offsets! Watch out for overflows, if FILTER_STRENGTH is too big! */
int16_t filterDec(int16_t inData)
{

    static int16_t average;
    static uint8_t startCounter;
    int32_t temp;
    
    if (startCounter<1)
    {   /* first value is the initialization for the average */
        startCounter++;
        average = inData*FILTER_SIZE;
    }
    temp = (int32_t)average*(FILTER_STRENGTH-1)+inData*FILTER_SIZE;
    average = (int16_t)(temp/FILTER_STRENGTH);
    return average;
}

 

The startCounter thing can be omitted, if you do not care, what happens during start-up.

Due to the integer division, the decaying filter will have some unwanted rounding effects.

If you have the memory, I propose the SMA filter, which actually needs only plus and minus.

 

In the beginning was the Word, and the Word was with God, and the Word was God.

Last Edited: Sun. Nov 9, 2014 - 01:17 AM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I skimmed the thread and did not see the obvious way of sign extending in C -- sorry if I missed it.

 

static inline int8_t sign_extend8(uint8_t val, uint8_t bits)

{

    uint8_t shift = 7 - bits;

    return (int8_t)(val << shift) >> shift;

}

 

static inline int16_t sign_extend16(uint16_t val, uint8_t bits)

{

    uint8_t shift = 15 - bits;

    return (int16_t)(val << shift) >> shift;

}

 

However since your value is 10 bits and we're on an LE 8bit MCU the fastest option is:

 

  uint8_t *arr = &val;

  arr[1] = sign_extend8(arr[1], 2);

 

Which should take just the 2 cycles, one LSL and one ASR, assuming the value is already in registers.

 

On your other questions, no the bitwise ops (|, &, ^) do not care about signed vs unsigned.

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

Some might prove to be a worthy of seeing other might not.

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

LOL -- I thought we killed this pig.

 

 

static inline int16_t sign_extend16(uint16_t val, uint8_t bits)

{

    uint8_t shift = 15 - bits;

    return (int16_t)(val << shift) >> shift;

}

So, let's take OP's case, with a "fixed" problem of AVR8 10-bit ADC result, to a 16-bit signed int. If the app is like mine, with continuous ADC sampling at, say, 200us each/10ksps, the sequence I proposed in #3 is less than a microsecond.  How many cycles will your routine take?  Hmmm--with CodeVision and Studio6.2 simulator, I get 2506 cycles.  300us at 8MHz. (Remember that I might want to do this in my app every 200us, and do a bunch of other stuff in my app as well...)

 

EDIT:  Making the routine not inline cut the cycle count to a more-expected 150.  20us at 8MHz.  [It could be a simulator artifact but a quick run-through indicated a possible situation with ... wait for it ... SIGN EXTENDING the shift count in the loop.  LOL]

 

The very practical AVR8 solution from #3 is SBRC/ORI.  2 cycles if the operand(s) are in high registers.

 

Thus the objections to the political-correctness.  But, I respect your beliefs. Just sayin'.

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.

Last Edited: Thu. Jan 8, 2015 - 08:20 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0
(int8_t)(val << shift) >> shift

According to the C99 standard, the result of the >> operator is implementation-defined for signed negative numbers.

This means, that we can not rely on the experience, that an arithmetic shift must be used (MSB is copied).

 

Also, reinterpretting the int16_t value as an array of two uint8_t values makes the code dependent on the endianess of the machine.

 

So, I would prefer the solution of comments #3 or #104.

In the beginning was the Word, and the Word was with God, and the Word was God.

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

skotti wrote:
According to the C99 standard, the result of the >> operator is implementation-defined for signed negative numbers.

This means, that we can not rely on the experience, that an arithmetic shift must be used (MSB is copied).

static_assert((-1)>>1==-1);

That said, the algorithm is really ugly and a tad obscure.

Quote:
So, I would prefer the solution of comments #3 or #104.
#3 is not as good as the algorithm OP started with. #1's use of 16-bit arithmetic is explicit and twos-complement is pretty much a given for AVRs.

I would change the presentation a little:

#include "20X.h"
...
int16_t result;
...
//#define SIGN_MASK 0x200
//#define SIGN_MASK (1<<9)
#define SIGN_MASK (1<<(SIGN_BITS-1))
if(result & SIGN_MASK) result |= -SIGN_MASK;

#104 would be good on a machine for which the absence of conditional code mattered.

Iluvatar is the better part of Valar.

Last Edited: Sat. Jan 10, 2015 - 04:04 PM

Pages