Anyway to simplify this PASM code snip? ... Golf challenge?

Beau Schwabe · 2012-01-25 10:24

weekend code project...
Does anyone see how this can be shortened? Not code wise, instruction wise... The section below "if_nz jmp #BitNotReady" needs to be deterministic. I would like to check for #%0110_0000 and #%0000_0110 also to determine the transition, but it's not a show stopper if that doesn't happen.

Prior to this block the raw Manchester data is read at 8 times the bit rate and rolled into a BYTE variable called "ManchesterBit" based on the result of the C flag. If the Bit transition is within the valid window, the "BitFlag" remains zero, otherwise an Error occurred and it is set to 1 where the 'BitSync' is dynamically incremented and eventually locks on to the data.

        rcl   ManchesterBit,    #1              'Move the 'C' flag into a BYTE     
                                                'that represents 1 Manchester Bit
        add   BitSync, #1
        and   BitSync, #%111    wz              'Keep value between 0 and 7

  if_nz jmp   #BitNotReady                      'Check if Manchester Bit is ready 

        mov   BitFlag,  #0                      'Valid Flag
        mov   t1,       ManchesterBit           'Test for bit transition (leading mis-alignment)
        and   t1,       #%0011_0000
        cmp   t1,       #16     wz
  if_nz cmp   t1,       #32     wz
  if_nz mov   t1,       ManchesterBit           'Test for bit transition (ideal alignment)
  if_nz and   t1,       #%0001_1000
  if_nz cmp   t1,       #8      wz
  if_nz cmp   t1,       #16     wz
  if_nz mov   t1,       ManchesterBit           'Test for bit transition (laging mis-alignment)
  if_nz and   t1,       #%0000_1100
  if_nz cmp   t1,       #4      wz
  if_nz cmp   t1,       #8      wz
  if_nz mov   BitFlag,  #1                      'Error Flag
  if_nz add   BitSync,  #1                      'dynamically adjust bit alignment

PossiblyValid
                          {Process ManchesterBit here}
BitNotReady

Phil Pilgrim (PhiPi) · 2012-01-25 11:00

Beau Schwabe wrote:

Not code wise, instruction wise...

By that do you mean "not, time-wise, space-wise" or vice-versa?

BTW, I've found that, for Manchester decoding, it's simpler to decode an entire string of bits both ways, then pick the result with the most decoded bits after you're done. It has the additional advantage of not discarding any data due to starting out of sync.

-Phil

Beau Schwabe · 2012-01-25 11:06

"By that do you mean "not, time-wise, space-wise" or vice-versa?" .... The code needs to be deterministic in the number of instructions.... i.e. If you rolled the code up into a loop it would take less code space, but you may not gain any execution speed, in fact it might be longer..... I need to gain execution speed by minimizing the required number of instructions to get the job done.

"BTW, I've found that, for Manchester decoding, it's simpler to decode an entire string of bits both ways, then pick the result with the most decoded bits after you're done." - Right but I wanted to decode on the fly without a buffer except for the final result.

ericball · 2012-01-25 11:16

Can you write what you want to do as a logic expression or pseudocode? I'm having trouble following the logic and there might be some optimizations if we can generate the whole logic block.

Hmm.. to start with you can replace the BitFlag ops with a single muxz instruction.

Phil Pilgrim (PhiPi) · 2012-01-25 11:24

Would this work?

        rcl   ManchesterBit,    #1              'Move the 'C' flag into a BYTE     
                                                'that represents 1 Manchester Bit
        add   BitSync, #1
        and   BitSync, #%111    wz              'Keep value between 0 and 7

  if_nz jmp   #BitNotReady                      'Check if Manchester Bit is ready 

        mov   BitFlag,  #0                      'Valid Flag
        mov   t1,       ManchesterBit           'Test for bit transition (leading mis-alignment)
        shl   t1,       #1
        xor   t1,       ManchesterBit           '1-bits at transitions.
        test  t1,       #%0010_0000 wz
  if_z  test  t1,       #%0001_0000 wz
  if_z  test  t1,       #%0000_1000 wz
  if_z  mov   BitFlag,  #1                      'Error Flag
  if_z  add   BitSync,  #1                      'dynamically adjust bit alignment

PossiblyValid
                          {Process ManchesterBit here}
BitNotReady

Or even better:

        rcl   ManchesterBit,    #1              'Move the 'C' flag into a BYTE     
                                                'that represents 1 Manchester Bit
        add   BitSync, #1
        and   BitSync, #%111    wz              'Keep value between 0 and 7

  if_nz jmp   #BitNotReady                      'Check if Manchester Bit is ready 

        mov   BitFlag,  #0                      'Valid Flag
        mov   t1,       ManchesterBit           'Test for bit transition (leading mis-alignment)
        shl   t1,       #1
        xor   t1,       ManchesterBit           '1-bits at transitions.
        test  t1,       #%0011_1000 wz
  if_z  mov   BitFlag,  #1                      'Error Flag
  if_z  add   BitSync,  #1                      'dynamically adjust bit alignment

PossiblyValid
                          {Process ManchesterBit here}
BitNotReady

-Phil

Beau Schwabe · 2012-01-25 12:19

Phil,

I knew there was a better way.... The last iteration you provided shaves 8 instructions from my original ... I'll have to look at it in closer detail later.

TEST of course... I changed the bit pattern to #%0011_1100

Thanks

Phil Pilgrim (PhiPi) · 2012-01-25 13:32

Beau Schwabe wrote:

I changed the bit pattern to #%0011_1100

That allows edges in four different positions, instead of three. Is that what you want?

Now we just have to wait for Kuroneko to wake up in Japan to shave off a few more instructions.

-Phil

pedward · 2012-01-25 15:20


'for pattern 0011_1100 rcr 4 and 6

       mov BitFlag, #0
       mov t1,       ManchesterBit           'Test for bit transition (leading mis-alignment
       rcr t1, #4 wc                         'check lower bit boundary
if_nc  rcr t1, #6 wc                         'check upper bit boundary
       rcl BitFlag, #1                       'if carry is zero, bit flag is zero, if carry is 1, bit flag is 1

Beau Schwabe · 2012-01-25 16:16

Phil, your right about the bits ... Should be %0011_1000

pedward,

WOW! ... but I'm not sure the C bit in the RCR works like you would think... "...C flag is set to Value's original bit 0." ... anyway I tried it and there was some jitter on the BitFlag.

The nature of the source of Manchester has a little jitter, so I need to be able to track or encompass the small movements.

pedward · 2012-01-25 16:27

Well, I didn't pickup that it was bit 0 going into the call. I read it as carry holding the last bit shifted out of the 0 place. IIRC, this is how it works on x86, it carries through. Curious, why doesn't it carry through like x86?

pedward · 2012-01-25 17:13

Perhaps this:

mov   BitFlag, ManchesterBit  'move data into flag
test  BitFlag, #%0011_1100 wz  'test for set and unset bits
muxnz BitFlag, #%11111111    'set all to 1 or all to 0 depending on test

pedward · 2012-01-25 17:16

Please forgive, the stupid editor keeps eating my binary digits!!!!!!

It could be reduced to andn BitFlag, # % 0011_1100 as long as you are just checking if Bitflag is non zero. Then it's 2 instructions.

Phil Pilgrim (PhiPi) · 2012-01-25 18:44

pedward,

What he's looking for is a transition (in either direction) between bits 3 and 2, 4 and 3, or 5 and 4: IOW any of the following six values:

**01****
**10****
***01***
***10***
****01**
****10**

where the stars represent "don't care" conditions.

-Phil

pedward · 2012-01-25 20:21

Beau, I researched it a bit more, and realize that in your case you are looking for 2 contiguous high bits surrounded by low bits.

Here's a thought, in an ideal sample you will always have 2 high bits, there should be ideally 2 low bits surrounding the high bits, but you are willing to accept a single low bit at each end.

The test instruction struck me as interesting because it stores parity in in the C flag and the test in Z.

So, if the possible values you are sampling are:

0110_0000
0011_0000
0001_1000
0000_1100
0000_0110

Then a mask of 0111_1110 would cover all of the valid high bits. Then if you do an AND on a valid result, you get 2 high bits and a match in Z.

The mask above would produce Z = 0 if a match was encountered and C = 0 if there were an even number of bits.

If you combine these you have TEST data, #%0111_1110 wz wc. If you have an even number of bits in the window, c = 0, so there are 2 high bits in the window. If z = then you know there was a match in the window.

If you match a single high bit in the window, c = 1. If there is 1 bit at the beginning of the window and 1 outside, it matches, but c = 1

So:

                mov  ErrFlag,   #1
                mov  OneBitErr, #0
                mov  NoDataErr, #0
                mov  t1,        ManchesterBit
                test t1,        #%0111_1110 wz wc
if_nc_and_nz    mov  ErrFlag,   #0
if_nz_and_c     mov  OneBitErr, #1
if_z            mov  NoDataErr, #1

This code gives you diagnostics to tune the rest of the code. If ErrFlag = 0 then a match was encountered. If OneBitErr is 1, you had only 1 bit in the window, if NoDataErr is set, then you had zero bits in the window.

Does this help?

Phil Pilgrim (PhiPi) · 2012-01-25 20:30

pedward wrote:

I researched it a bit more, and realize that in your case you are looking for 2 contiguous high bits surrounded by low bits.

That's not what he's looking for. He's looking for a transition near the center of the sample window (ref: http://en.wikipedia.org/wiki/Manchester_code).

-Phil

pedward · 2012-01-25 20:39

I read the same page, but he is 8x oversampling it, so a high is actually a string of high bits, in his case he is looking for 2 contiguous high bits for 1 signal high. The code above allows you to change the window width with the mask, so you can tune your center that way.

I re-read his original request and based on the code posted and his request (including the "wouldn't it be nice"), I produced the above test.

Phil Pilgrim (PhiPi) · 2012-01-25 20:45

pedward wrote:

in his case he is looking for 2 contiguous high bits for 1 signal high.

Nope, sorry. A low is a low-to-high transition in the middle of the sample frame. A high is a high-to-low transition in the middle of the sample frame. The purpose of Beau's posted code is to synchronize to the incoming signal, so that transitions always occur near the center of the sample frame, not off to one side.

-Phil

pedward · 2012-01-25 21:03

Damn forum ate my post when I hit Ctrl-C.

{ some stuff about visualizing data, blah blah, I missed the original point }

If the code I wrote is changed to check for an odd number of bits, then a bit transition happened in the window.

Further, you can make it a call and tune the window as such:

test bits, 0111_1110 'test for transition in window
test bits, 1000_0000 'test for transition at MSB

if first test false and second test true, data is at MSB of sample, else data is at LSB of sample

repeat the tests with smaller windows after each clock adjustment:

test bits, 0011_1100 'test window
test bits, 1100_0000 'test for bits at MSB of sample

test bits, 0001_1000 'test window
test bits, 1110_0000 'test MSB

if in 3 rounds of clock adjustment you haven't gotten a true result, then something isn't right. a correct result is z = 0 and c = 1 for a test with 1 transition within the test window.

Further, this test works to test if you have 2 samples in the window, because z = 0 and c = 0, which tells you your clocking is too slow. This test should give all sorts of diagnostics with only a few instructions.

jazzed · 2012-01-25 22:51

Hi Beau. 10Mb Ethernet receiver? "Impossible"

Cheers.

Phil Pilgrim (PhiPi) · 2012-01-25 22:56

pedward wrote:

If the code I wrote is changed to check for an odd number of bits, then a bit transition happened in the window.

--0001-- = odd
--0011-- = even
--0111-- = odd
--1110-- = odd
--1100-- = even
--1000-- = odd

All valid transitions.

-Phil

pedward · 2012-01-26 00:16

Phil Pilgrim (PhiPi) wrote: »

--0001-- = odd
--0011-- = even
--0111-- = odd
--1110-- = odd
--1100-- = even
--1000-- = odd

All valid transitions.

-Phil

When he says he's 8x oversampling the data, I take that to mean there is 1 potential symbol in the 8 bits, is this incorrect? If there is 1 symbol in 8 bits then my algorithm works correctly. If there are multiple symbols in the 8 bits, then it doesn't work.

kuroneko · 2012-01-26 04:31

[POC]: The received/constructed byte (bit 8 is assumed clear) is used as table index. jmpret's carry behaviour is unsigned borrow, i.e. comparing the continue label against 0 (shadow[par]) sets carry (NG) and clears it when compared to the jmpret insn itself (OK).

DAT             org     0

entry           jmp     #main

{OK}            jmpret  $,   #continue wc,nr
{OK}            [COLOR="blue"]jmpret  $,   #continue wc,nr[/COLOR]

' locations 0..255 are occupied by OK/NG jmprets
' example: 0 - NG
'          1 - OK
'          2 - OK
'        255 - NG

                long    0[252]
{NG}            [COLOR="blue"]jmpret  par, #continue wc,nr[/COLOR]

main            mov     $000, $-1               ' restore zero index (NG)

                ...

        if_nz   jmp     #BitNotReady            ' Check if Manchester Bit is ready
'-----------------------------------------------
[COLOR="orange"]                jmp     ManchesterBit
continue        muxc    BitFlag, #1
                addx    BitSync, #0             '
[/COLOR]'-----------------------------------------------
PossiblyValid
                {Process ManchesterBit here}
BitNotReady

Phil Pilgrim (PhiPi) · 2012-01-26 08:01

pedward wrote:

When he says he's 8x oversampling the data, I take that to mean there is 1 potential symbol in the 8 bits, is this incorrect?

It means that he samples the input line eight times for each bit. There will always be at most one edge in that 8-bit frame, so the possible values he can receive from this are:

00[b]0000[/b]00
00[b]0000[/b]01
00[b]0000[/b]11
00[b]0001[/b]11
00[b]0011[/b]11
00[b]0111[/b]11
00[b]1111[/b]11
01[b]1111[/b]11
11[b]1111[/b]11
11[b]1111[/b]10
11[b]1111[/b]00
11[b]1110[/b]00
11[b]1100[/b]00
11[b]1000[/b]00
11[b]0000[/b]00
10[b]0000[/b]00

When the edge occurs in the center (boldface portion) of the byte, the code is in sync with the incoming signal. Otherwise the sampling phase has to be advanced for another try.

-Phil

pedward · 2012-01-26 09:48

So, ideal symbols contain an even number of high bits OUTSIDE the sync window AND the bits inside the sync window are less than $F.

So:

              mov  Bitflag,    #1                   'set error
              mov  t1,         manniesbits          'get sample
              test t1,         # % 1100_0011 wz wc  'test for even number of high bits outside of sync window
if_nz_and_nc  and  t1,         # % 0011_1100 wz     'if there are even number of high bits outside window, check for bits inside
if_nz         cmp  t1,         #$F wc               'if a match to the mask, test for NOT all high bits
if_c          mov  BitFlag,    #0                   'if sync window not all high bits

This code looks for a solid high bit pattern outside the sync window, then looks for a transition inside the window. You could make the window wider, per Beau's request, and the code would still work with the new values. This code would break if not using 8x oversampling.

EDIT: remove test for flag, crazy editor keeps inserting empty code tags!

kuroneko · 2012-01-26 16:11

Phil Pilgrim (PhiPi) wrote: »

It means that he samples the input line eight times for each bit. There will always be at most one edge in that 8-bit frame, so the possible values he can receive from this are:

Last time I checked Manchester encoding symbols are based on transitions in the middle of the bit, i.e. for two zero or one symbols wouldn't you (worst case) only have 4 bits high, i.e. checking edges at %0110000110 may be ambiguous (since you slipped by half a symbol)?

pedward · 2012-01-26 16:36

I think he is sampling 1 symbol 8x over.

Phil Pilgrim (PhiPi) · 2012-01-26 17:00

pedward wrote:

I think he is sampling 1 symbol 8x over.

Correct.

kuroneko · 2012-01-26 17:15

OK, so maye that's down to a misunderstanding. I thought that each of the 8 bits of the ManchesterBit variable holds an 8th of the incoming symbol.

|    1    |
       +----+    +-
       |    |    |
      -+    +----+

        1111_0000

Phil Pilgrim (PhiPi) · 2012-01-26 18:26

Kuroneko,

Your diagram is correct, as far as my understanding of the problem goes. Beau is oversampling the input so he can adjust synchronization to get the transitions in the center of the bit window. The use of the word "symbol" rather than "bit window" is probably what made things confusing.

-Phil

kuroneko · 2012-01-26 18:49

To extend this a bit (HA!), having two consecutive one bits would make it possible to sample %11000011. Beau mentioned in his original post that edges %01100000 and %00000110 would be nice to have. But I'd argue then they would possibly be flagged as OK when they are not (although their treatment - if detected - hasn't been explicitly stated).

|    1    |    1    |
       +----+    +----+    +-
       |    |    |    |    |
      -+    +----+    +----+

          1[COLOR="orange"]1_0[/COLOR]00[COLOR="orange"]0_1[/COLOR]1
               0[COLOR="orange"]0_1[/COLOR]11[COLOR="orange"]1_0[/COLOR]0

kuroneko · 2012-01-26 19:54

pedward wrote: »

              mov  Bitflag,    #1                   'set error
              mov  t1,         manniesbits          'get sample
              test t1,         #%1100_0011 wz,wc    'test for even number of high bits outside of sync window
if_nz_and_nc  and  t1,         #%0011_1100 wz       'if there are even number of high bits outside window, check for bits inside
if_nz         cmp  t1,         #$F wc               'if a match to the mask, test for NOT all high bits
if_c          mov  BitFlag,    #0                   'if sync window not all high bits

I don't see this working with %11110000 and %00001111. Both are valid edges but BitFlag is set to opposing values. It's easy enough to fix but ...

Anyway to simplify this PASM code snip? ... Golf challenge?

Comments