Mini-challenge: detecting activity on a port

[BigEd]

Here's a mini-challenge for you. I have a real application in mind too, so it's not artificial.

You have an 8 bit input port at some absolute address, and the challenge is to write a subroutine which waits for every pin to toggle (change state) at least twice, and then returns. (It should of course return as soon as every pin has toggled twice, regardless of the starting state of the inputs and the order in which they toggle. They might all change together, or one by one.)

For example, if the port initially reads 00, then the next read is FF, and the next read is 00, we're done. Or if the first read is 01, then 02, shifting left to 80, then 01 again, we'd be done. Or it might take thousands of samples: it might even never happen. There might be many repeated values, or no repeats at all.

Edit: adding a bit of padding to keep replies further down the page...
.
..
.
...
.
..
.
....
.
..
.
...
.
..
.

[Chromatix]

Oh, this looks fun! My approach would use three bytes of ZP; one maintaining the previous state of the port, and two masks indicating whether the first and second transitions have occurred on each bit; I think that's the minimum required to function. And I'm going to use CMOS instructions.

Code: Select all

port = $xxxx
zp = $zz

prev = zp+0
first = zp+1
second = zp+2

WaitPort8:
  ; initialise
  LDA port
  STA prev
  STZ first
  LDA #$FF
  STA second

  ; main loop
: LDA port
  TAX
  EOR prev
  BEQ :-      ; speed optimisation, omit if size critical
  STX prev
  TAX          ; mask of changed bits
  AND first    ; bits that have already changed once; this is their second
  TRB second   ; clear them out of the terminating condition
  TXA          ; return to bits just changed
  TSB first    ; record that fact
  LDA second   ; now test to see if all flags cleared
  BNE :-
  RTS

This is 34 bytes, or 32 if you leave out the early loopback which reduces port response latency. One further byte can be saved at a slight speed penalty by inverting the polarity of the second register:

Code: Select all

port = $xxxx
zp = $zz

prev = zp+0
first = zp+1
second = zp+2

WaitPort8:
  ; initialise
  LDA port
  STA prev
  STZ first
  STZ second

  ; main loop
: LDA port
  TAX
  EOR prev
  STX prev
  TAX          ; mask of changed bits
  AND first    ; bits that have already changed once; this is their second
  TSB second   ; set them in the terminating condition
  TXA          ; return to bits just changed
  TSB first    ; record that fact
  LDX second   ; now test to see if all second flags set
  INX
  BNE :-
  RTS

The above is 31 bytes. This form is also easier to convert to be NMOS compatible, by replacing each TSB with ORA/STA and doing the usual fix on STZ, but this adds 6 bytes to the code size and 2 cycles to the sampling interval.

In the first example, the port is sampled every 12 cycles if it hasn't changed in any bit, with a gap of 37 cycles if it has. If the short-circuit is removed, the sampling interval becomes a consistent 35 cycles. The second example takes 37 cycles consistently. These characteristics will define timing requirements for the external hardware, in terms of the shortest pulse that will consistently be detected; at 8MHz CPU clock, 40 cycles (5µs) might be considered safe.

[rudla.kudla]

Same idea here. 6502 instruction set.

Code: Select all

ch_1	= 129
ch_2   = 130

	org $2000
START
			lda #0
			sta ch_1
			sta ch_2
			lda test
			sta prev

			ldy #1
@			lda test,y
			jsr REGISTER
			iny
			cpy #test_end-test
			bne @-

loop		jmp loop
			rts

REGISTER
			tax
			eor prev
			stx prev
			tax

			and ch_1
			ora ch_2		;leave only those, that were previously set to 0
			sta ch_2

			txa
			ora ch_1		;accumulate 1 bits
			sta ch_1

;##TRACE  "%08b %08b %08b" db(prev) db(ch_1) db(ch_2)

			lda ch_2
			cmp #$FF			;Z = 1 - done
			rts
test
			dta %00000010
			dta %00000011
			dta %00000001
			dta %00000111
			dta %00000110
			dta %00000100
			dta %11111000
			dta %00000000
test_end

[leepivonka]

Code: Select all

WaitFor2Changes:
    lda port    ; remember initial values
    sta @orig
    stz @change1    ; no 1st changes yet
    stz @change2    ; no 2nd changes yet

@loop:
    lda port    ; get changes
    eor @orig
    sta @temp1

    ora @change1    ; accum 1st change
    sta @change1

    eor @temp1  ; accum 2nd change
    ora @change2
    sta @change2

    ina     ; until all 2nd change set
    bne @loop

    rts

@orig:  .byte       ; original value
@change1: .byte     ; 1st change seen
@change2: .byte     ; 2nd change seen
@temp1  .byte       ; temporary

[Chromatix]

That is an interesting alternative approach. Essentially you're looking for bits to be set and then cleared, after first transforming them relative to the first value read, rather than explicitly looking for two changes between successive reads. It's potentially a little smaller code than mine, but requires an extra byte of storage.

As written, it would end up quite large because of the locally-allocated storage (which requires absolute addressing). If you move the variables into ZP, it's 30 bytes.

[commodorejohn]

Oh, interesting...gonna have to have a think on this one.

[dmsc]

Hi!

BigEd wrote:

Here's a mini-challenge for you. I have a real application in mind too, so it's not artificial.

You have an 8 bit input port at some absolute address, and the challenge is to write a subroutine which waits for every pin to toggle (change state) at least twice, and then returns. (It should of course return as soon as every pin has toggled twice, regardless of the starting state of the inputs and the order in which they toggle. They might all change together, or one by one.)

This kind of problem (having to perform logic for all bits in a byte/word) can be solved by a technique called "vertical counters", see https://everything2.com/title/vertical+counter for a little explanation.

In your case, you can define a state machine with three states, representing the number of transitions seen, state A, B and C. You got from A to B of from B to C if you detect a transition, and do nothing in all other cases. If you encode with two bits, "x" and "y", using A = "00", B = "01" and "C = "11", your logic table is:

Code: Select all

In xy  x'y'
-----------
0  00   00
0  01   01
0  10   --
0  11   11
1  00   01
1  01   11
1  10   --
1  11   11

This simplifies to the two equations: x' = x+I*y and y' = y + I.

Now, the (untested) code:

Code: Select all

   ' Three ZP locations for our variables:
OLD_IN = $10
S_X = $11
S_Y = $12

wait:
   ' Init old input var
   lda INPUTS
   sta OLD_IN
   lda #0
   ldy #0
loop:
   ' Store state
   sta S_X
   sty S_Y
   ' Check toggled bits updating old value
   lda OLD_IN
   tax
   eor INPUTS
   stx OLD_IN
   ' Store for later
   tax
   ' Now, get new Y
   ora S_Y
   tay
   ' And the get new X
   txa
   and S_Y
   ora S_X
   ' Compare X with 255 (al bits set)
   cmp #255
   bne loop
   ' Ok!
   rts

Have Fun!

[Chromatix]

I count 35 bytes, 38 cycles per loop, and at least one visible bug…

Otherwise, it's conceptually similar to my solution, just implemented differently.

[BigEd]

Hope everyone's having fun! Great to see the code posted. (For myself, I think my vague idea was to register rising transitions in one byte's worth of bits, and register falling transitions in another. When both of those bytes fill up we're done. But I hadn't written any code. There's always more than one way to do it!)

[Chromatix]

BigEd wrote:

Hope everyone's having fun! Great to see the code posted. (For myself, I think my vague idea was to register rising transitions in one byte's worth of bits, and register falling transitions in another. When both of those bytes fill up we're done. But I hadn't written any code. There's always more than one way to do it!)

Hmm, sketching out that idea:

Code: Select all

  LDA port
  STA prev
  LDA #$FF
  STA first
  STA second

: LDA port
  TAX
  EOR prev
  BEQ :-      ; speed optimisation, omit if size critical
  AND prev     ; falling transitions have bits set
  TRB falling
  TXA
  EOR #$FF
  ORA prev    ; rising transitions have bits cleared
  AND rising
  STA rising
  STX prev
  ORA falling
  BNE :-
  RTS

That makes 39 bytes, and I'm not even going to bother counting the cycles. It just turns out to be more awkward to identify the specific transitions rather than just looking for *any* transition.

[dmsc]

Hi!

Chromatix wrote:

I count 35 bytes, 38 cycles per loop, and at least one visible bug…

Otherwise, it's conceptually similar to my solution, just implemented differently.

Yes, I saw your code after posting mine, I tried to show how to arrive at a generic solution because I have used vertical-counters in microcontrollers before, for debouncing and general counting of transitions.

Also, my code is 6502 only, and I still don't see the bug yet

Have Fun!

[dmsc]

Hi!

dmsc wrote:

Hi!

Chromatix wrote:

I count 35 bytes, 38 cycles per loop, and at least one visible bug…

Otherwise, it's conceptually similar to my solution, just implemented differently.

Yes, I saw your code after posting mine, I tried to show how to arrive at a generic solution because I have used vertical-counters in microcontrollers before, for debouncing and general counting of transitions.

Also, my code is 6502 only, and I still don't see the bug yet

Have Fun!

Now I see it, fixed code bellow:

Code: Select all

   ' Three ZP locations for our variables:
OLD_IN = $10
S_X = $11
S_Y = $12

wait:
   ' Init old input var
   lda INPUTS
   sta OLD_IN
   lda #0
   ldy #0
loop:
   ' Store state
   sta S_X
   sty S_Y
   ' Check toggled bits updating old value
   lda INPUT
   tax
   eor OLD_IN
   stx OLD_IN
   ' Store for later
   tax
   ' Now, get new Y
   ora S_Y
   tay
   ' And the get new X
   txa
   and S_Y
   ora S_X
   ' Compare X with 255 (al bits set)
   cmp #255
   bne loop
   ' Ok!
   rts

Have Fun!

[barrym95838]

I haven't tried to analyze anyone else's code yet, and started with a clean sheet of paper and a #2 pencil (I'll be using the NMOS instruction set obviously) ...

Code: Select all

attempt:
    lda  #0        ; initialize bit trackers
    sta  once
    tax
cont:
    sta  twice     ; track bits that flipped >= twice
    txa
    ora  once      ; 1s for bits that flipped >= once
    sta  once      ; track bits that flipped >= once
    ldx  PORT
wait:
    txa
    eor  PORT      ; wait for some PORT activity
    beq  wait
    tax            ; 1s for bits that flipped this time
    and  once
    ora  twice     ; 1s for bits that flipped >= twice
    cmp  #$ff      ; have all 8 bits flipped >= twice?
    bne  cont
    rts

I don't have any time to test it, because I'm sneaking it in at work, but it looks like I did it in 30 bytes +RTS +two bytes of ZP. I'll try to test it tonight, but I would certainly appreciate any early feedback from you guys. Thanks,

[Chromatix]

Hmm, I spy a race condition in that last one. When any bit transition is seen, any future transitions are only detected relative to a second port read. So any transitions occurring between those two reads will be lost.

[barrym95838]

I must be a bit confused or near-sighted, because I don't immediately see how I'll miss any port transition events unless they burst less than ~30 cycles apart, which is about how long my routine takes to allegedly close its eyes to digest each event. I guess I'll have to try to grok what the rest of you have posted to see where I failed ...

Would this one have a smaller "blind spot"? (it's one byte smaller too, and still NMOS, baby!)

Code: Select all

attempt2:
    lda  #0        ; initialize bit trackers
    sta  once
cont:
    sta  twice     ; track bits that flipped >= twice
    beq  first
    txa
    ora  once      ; 1s for bits that flipped >= once
    sta  once      ; track bits that flipped >= once
    tya
    eor  PORT      ; check for PORT activity
first:
    ldy  PORT
    tax            ; 1s for bits that flipped this time
    and  once
    ora  twice     ; 1s for bits that flipped >= twice
    cmp  #$ff      ; have all 8 bits flipped >= twice?
    bne  cont
    rts