Z80 Routines:Optimized:PopCountA - Revision history

Calc84maniac: Add more optimized popcount

2024-04-26T18:37:30Z

Add more optimized popcount

Jacobly at 03:49, 16 September 2020

2020-09-16T03:49:54Z

Jacobly at 03:37, 16 September 2020

2020-09-16T03:37:36Z

Jacobly at 03:36, 16 September 2020

2020-09-16T03:36:22Z

Jacobly at 03:35, 16 September 2020

2020-09-16T03:35:38Z

Jacobly: Created page with "PopCountA PopCountA This is a faster/smaller (and also obfuscated) replacement for the normal popcount a, which r..."

2020-09-16T03:17:09Z

Created page with "PopCountA PopCountA This is a faster/smaller (and also obfuscated) replacement for the normal popcount a, which r..."

New page

[[Category:Z80 Routines:Optimized|PopCountA]]
[[Category:Z80 Routines|PopCountA]]
This is a faster/smaller (and also obfuscated) replacement for the normal popcount a, which returns the number of set bits in a.

Typical routine:
<nowiki>;input: b
;output: a
;27 bytes, 108 clock cycles
TypicalPopCountA:
ld c,a
xor a
ld b,a
rrc c
adc a,b
rrc c
adc a,b
rrc c
adc a,b
rrc c
adc a,b
rrc c
adc a,b
rrc c
adc a,b
rrc c
adc a,b
rrc c
adc a,b</nowiki>

Better routine:
<nowiki>;- Pop Count A
;input: byte in A
;output: number of set bits in A
;destroys BC
;22 bytes and 85 clock cycles
;author: jacobly
PopCountA:
ld c, a
and 10101010b
cpl
rrca
adc a, c
ld b, a
and 00110011b
ld c, a
xor b
rrca
rrca
add a, c
ld c, a
rrca
rrca
rrca
rrca
add a, c
and 00001111b</nowiki>

← Older revision		Revision as of 18:37, 26 April 2024
Line 51:		Line 51:
	add a, c ; a=(A+B+C+D+E+F+G+H\|A+B+C+D+E+F+G+H)		add a, c ; a=(A+B+C+D+E+F+G+H\|A+B+C+D+E+F+G+H)
	and 00001111b ; a=A+B+C+D+E+F+G+H</nowiki>		and 00001111b ; a=A+B+C+D+E+F+G+H</nowiki>
		+
		+	Even better routine, making the following observations:
		+
		+	<nowiki>
		+	a = (a>>1) + (a>>1) + (a&1)
		+	a = (a>>1) + ((a>>2) + (a>>2) + ((a>>1)&1)) + (a&1)
		+	...
		+	a = (a>>1) + (a>>2) + ... + (a>>7) + (a>>7) + ((a>>6)&1) + ... + ((a>>1)&1) + (a&1)
		+	a - (a>>1) - (a>>2) - ... - (a>>7) = (a>>7) + ((a>>6)&1) + ... + ((a>>1)&1) + (a&1)</nowiki>
		+
		+	<nowiki>;- Pop Count A
		+	;input: byte in a
		+	;output: number of set bits in a
		+	;destroys f, c
		+	;21 bytes and 84 clock cycles
		+	;author: calc84maniac
		+	PopCountA:
		+	; a -= (byte>>7)
		+	ld c, a
		+	add a, c
		+	sbc a, c
		+	; a -= (byte>>1)
		+	srl c
		+	sub c
		+	; a -= (byte>>2)
		+	srl c
		+	sub c
		+	; a -= (byte>>3)
		+	srl c
		+	sub c
		+	; a -= (byte>>4)
		+	srl c
		+	sub c
		+	; a -= (byte>>5)
		+	srl c
		+	sub c
		+	; a -= (byte>>6)
		+	srl c
		+	sub c</nowiki>
		+
		+	This algorithm can also be used to implement a size-optimized routine:
		+	<nowiki>;- Pop Count A
		+	;input: byte in a
		+	;output: number of set bits in a
		+	;destroys f, c
		+	;7 bytes and 26-194 clock cycles
		+	;author: calc84maniac
		+	PopCountA:
		+	ld c, a
		+	.db $FE ;CP imm8, skips subtracting c on the first iteration
		+	.loop:
		+	sub c
		+	srl c
		+	jr nz, .loop</nowiki>

@@ Line 45: / Line 45: @@
 	ld	c, a			; c=(00|C+D|00|G+H)
 	xor	b			; a=(A+B|00|E+F|00)
-	rrca \ rrca			; a=(0|A+B|00|E+F|0)
+	rrca \ rrca			; a=(00|A+B|00|E+F)
 	add	a, c			; a=(A+B+C+D|E+F+G+H)
 	ld	c, a			; c=(A+B+C+D|E+F+G+H)

@@ Line 7: / Line 7: @@
 ;output: a
 ;destroys: f, c
-;27 bytes, 108 clock cycles
+;26 bytes, 104 clock cycles
 TypicalPopCountA:
 	xor	a

@@ Line 6: / Line 6: @@
   <nowiki>;input: b
 ;output: a
 ;27 bytes, 108 clock cycles
 TypicalPopCountA:
@@ Line 29: / Line 30: @@
 Better routine:
   <nowiki>;- Pop Count A
-;input:	byte in A
+;input:	byte in a
-;output: number of set bits in A
+;output: number of set bits in a
-;destroys BC
+;destroys f, bc
 ;22 bytes and 85 clock cycles
 ;author: jacobly

@@ Line 8: / Line 8: @@
 ;27 bytes, 108 clock cycles
 TypicalPopCountA:
 	xor	a
-	ld	b,a
+	ld	c, a
-	rrc	c
+	rrc	b
-	adc	a,b
+	adc	a, c
-	rrc	c
+	rrc	b
-	adc	a,b
+	adc	a, c
-	rrc	c
+	rrc	b
-	adc	a,b
+	adc	a, c
-	rrc	c
+	rrc	b
-	adc	a,b
+	adc	a, c
-	rrc	c
+	rrc	b
-	adc	a,b
+	adc	a, c
-	rrc	c
+	rrc	b
-	adc	a,b
+	adc	a, c
-	rrc	c
+	rrc	b
-	adc	a,b
+	adc	a, c
-	rrc	c
+	rrc	b
-	adc	a,b</nowiki>
+	adc	a, c</nowiki>
 Better routine:
@@ Line 36: / Line 35: @@
 ;author: jacobly
 PopCountA:
-	ld	c, a
+	ld	c, a			; c=(A|B|C|D|E|F|G|H)
-	and	10101010b
+	and	10101010b		; a=(A|0|C|0|E|0|G|0)
-	cpl
+	cpl				; a=(~A|1|~C|1|~E|1|~G|1)
-	rrca
+	rrca				; a=(1|~A|1|~C|1|~E|1|~G), cf=1
-	adc	a, c
+	adc	a, c			; a=(A+B|C+D|E+F|G+H)
-	ld	b, a
+	ld	b, a			; b=(A+B|C+D|E+F|G+H)
-	and	00110011b
+	and	00110011b		; a=(00|C+D|00|G+H)
-	ld	c, a
+	ld	c, a			; c=(00|C+D|00|G+H)
-	xor	b
+	xor	b			; a=(A+B|00|E+F|00)
-	rrca
+	rrca \ rrca			; a=(0|A+B|00|E+F|0)
-	rrca
+	add	a, c			; a=(A+B+C+D|E+F+G+H)
-	add	a, c
+	ld	c, a			; c=(A+B+C+D|E+F+G+H)
-	ld	c, a
+	rrca \ rrca \ rrca \ rrca	; a=(E+F+G+H|A+B+C+D)
-	rrca
+	add	a, c			; a=(A+B+C+D+E+F+G+H|A+B+C+D+E+F+G+H)
-	rrca
+	and	00001111b		; a=A+B+C+D+E+F+G+H</nowiki>
-	rrca
-	rrca
 	add	a, c
 	and	00001111b</nowiki>