|
Título: aPLib, rutinas optimizadas Publicado por: Metalbrain en 27 de Enero de 2013, 01:55:42 pm Hace poco también estuve optimizando un poquito las rutinas de aPLib, otra buena alternativa para comprimir datos, así que ya va siendo hora de que las presente por aquí también. Como ventajas sobre exomizer:
- no necesita reservar memoria para una tabla temporal de 156 bytes. - no añade una tabla de 26 bytes fijos al comienzo de los datos comprimidos, por lo que tiene más posibilidades de comprimir bloques pequeños de datos - para bloques grandes, en muy raras ocasiones, comprime mejor (pero el 95% de las veces gana exomizer, que conste) - más rápida (aunque ya no tanto tras las últimas optimizaciones de exomizer) Podeis encontrar el programa compresor (appack.exe) aquí, junto con el descompresor original sin optimizar (muy muy lento): http://www.smspower.org/maxim/uploads/SMSSoftware/aplib12.zip Rutina optimizada en tamaño (156 bytes): Código: ; aPPack decompressor ; original source by dwedit ; very slightly adapted by utopian ; optimized by Metalbrain ;hl = source ;de = dest depack: ld ixl,128 apbranch1: ldi aploop0: ld ixh,1 ;LWM = 0 aploop: call ap_getbit jr nc,apbranch1 call ap_getbit2 jr nc,apbranch2 ld bc,16 call ap_getbit2 jr nc,apbranch3 apget4bits: call ap_getbit2 rl c jr nc,apget4bits ld a,b jr z,apwritebyte and a ex de,hl ;write a previous byte (1-15 away from dest) sbc hl,bc ld a,(hl) add hl,bc ex de,hl apwritebyte: ld (de),a ;write a 0 inc de jr aploop0 apbranch3: ld c,(hl) ;use 7 bit offset, length = 2 or 3 rr c ret z ;if a zero is found here, it's EOF inc hl ld a,b adc a,2 push hl push bc pop iy ld h,d ld l,e sbc hl,bc ld c,a jr ap_finishup2 apbranch2: call ap_getgamma ;use a gamma code * 256 for offset, another gamma code for length dec c ld a,c sub ixh jr z,ap_r0_gamma ;if gamma code is 2, use old r0 offset, dec a ;do I even need this code? ;bc=bc*256+(hl), lazy 16bit way ld b,a ld c,(hl) inc hl push bc pop iy push bc call ap_getgamma ex (sp),hl ;bc = len, hl=offs push de ex de,hl ld a,4 cp d jr nc,apskip2 inc bc or a apskip2: ld hl,127 sbc hl,de jr c,apskip3 inc bc inc bc apskip3: pop hl ;bc = len, de = offs, hl=junk push hl or a ap_finishup: sbc hl,de pop de ;hl=dest-offs, bc=len, de = dest ap_finishup2: ldir pop hl ld ixh,b jr aploop ap_r0_gamma: call ap_getgamma ;and a new gamma code for length push hl push de ex de,hl push iy pop de jr ap_finishup ap_getbit: ld a,ixl ap_getbit2: add a,a jr nz,ap_endbit ld a,(hl) inc hl rla ap_endbit: ld ixl,a ret ap_getgamma: ld bc,1 ap_getgammaloop:call ap_getbit rl c rl b call ap_getbit2 jr c,ap_getgammaloop ret Rutina optimizada en velocidad (197 bytes): Código: ; aPPack decompressor ; original source by dwedit ; very slightly adapted by utopian ; optimized by Metalbrain ;hl = source ;de = dest depack: ld a,128 apbranch1: ldi aploop2: ld ixh,1 aploop: add a,a jr nz,apnogetbit1 ld a,(hl) inc hl rla apnogetbit1: jr nc,apbranch1 add a,a jr nz,apnogetbit2 ld a,(hl) inc hl rla apnogetbit2: jr nc,apbranch2 add a,a jr nz,apnogetbit3 ld a,(hl) inc hl rla apnogetbit3: jr nc,apbranch3 ld bc,16 ;get an offset apget4bits: add a,a jr nz,apnogetbit4 ld a,(hl) inc hl rla apnogetbit4: rl c jr nc,apget4bits jr nz,apbranch4 ex de,hl ld (hl),b ;write a 0 ex de,hl inc de jp aploop2 apbranch4: ex af,af' ex de,hl ;write a previous byte (1-15 away from dest) sbc hl,bc ld a,(hl) add hl,bc ld (hl),a ex af,af' ex de,hl inc de jp aploop2 apbranch3: ld c,(hl) ;use 7 bit offset, length = 2 or 3 inc hl ex af,af' rr c ret z ;if a zero is found here, it's EOF ld a,2 ld b,0 adc a,b push hl ld iyh,b ld iyl,c ld h,d ld l,e sbc hl,bc ld c,a ex af,af' ldir pop hl ld ixh,b jp aploop apbranch2: call ap_getgamma ;use a gamma code * 256 for offset, another gamma code for length dec c ex af,af' ld a,c sub ixh jr z,ap_r0_gamma dec a ;do I even need this code? ;bc=bc*256+(hl), lazy 16bit way ld b,a ld c,(hl) inc hl ld iyh,b ld iyl,c push bc call ap_getgamma2 ex (sp),hl ;bc = len, hl=offs push de ex de,hl ex af,af' ld a,4 cp d jr nc,apskip2 inc bc or a apskip2: ld hl,127 sbc hl,de jr c,apskip3 inc bc inc bc apskip3: pop hl ;bc = len, de = offs, hl=junk push hl or a sbc hl,de ex af,af' pop de ;hl=dest-offs, bc=len, de = dest ldir pop hl ld ixh,b jp aploop ap_r0_gamma: call ap_getgamma2 ;and a new gamma code for length push hl push de ex de,hl ld d,iyh ld e,iyl sbc hl,de pop de ;hl=dest-offs, bc=len, de = dest ldir pop hl ld ixh,b jp aploop ap_getgamma2: ex af,af' ap_getgamma: ld bc,1 ap_getgammaloop:add a,a jr nz,apnogetbit5 ld a,(hl) inc hl rla apnogetbit5: rl c rl b add a,a jr nz,apnogetbit6 ld a,(hl) inc hl rla apnogetbit6: jr c,ap_getgammaloop ret Título: Re: aPLib, rutinas optimizadas Publicado por: Metalbrain en 27 de Enero de 2013, 01:56:02 pm Se puede aumentar la velocidad más todavía, expandiendo la rutina ap_getgamma de forma que pongamos inline los primeros pasos de la rutina, al precio de 15 bytes por cada bit optimizado (hasta el octavo, luego 17 hasta el 15 que sería el último). Aquí pongo un ejemplo con 2 bits optimizados (227 bytes):
Código: ; aPPack decompressor ; original source by dwedit ; very slightly adapted by utopian ; optimized by Metalbrain ;hl = source ;de = dest depack: ld a,128 apbranch1: ldi aploop2: ld ixh,1 aploop: add a,a jr nz,apnogetbit1 ld a,(hl) inc hl rla apnogetbit1: jr nc,apbranch1 add a,a jr nz,apnogetbit2 ld a,(hl) inc hl rla apnogetbit2: jr nc,apbranch2 add a,a jr nz,apnogetbit3 ld a,(hl) inc hl rla apnogetbit3: jr nc,apbranch3 ld bc,16 ;get an offset apget4bits: add a,a jr nz,apnogetbit4 ld a,(hl) inc hl rla apnogetbit4: rl c jr nc,apget4bits jr nz,apbranch4 ex de,hl ld (hl),b ;write a 0 ex de,hl inc de jp aploop2 apbranch4: ex af,af' ex de,hl ;write a previous byte (1-15 away from dest) sbc hl,bc ld a,(hl) add hl,bc ld (hl),a ex af,af' ex de,hl inc de jp aploop2 apbranch3: ld c,(hl) ;use 7 bit offset, length = 2 or 3 inc hl ex af,af' rr c ret z ;if a zero is found here, it's EOF ld a,2 ld b,0 adc a,b push hl ld iyh,b ld iyl,c ld h,d ld l,e sbc hl,bc ld c,a ex af,af' ldir pop hl ld ixh,b jp aploop apbranch2: call ap_getgamma ;use a gamma code * 256 for offset, another gamma code for length dec c ex af,af' ld a,c sub ixh jr z,ap_r0_gamma dec a ;do I even need this code? ;bc=bc*256+(hl), lazy 16bit way ld b,a ld c,(hl) inc hl ld iyh,b ld iyl,c push bc call ap_getgamma2 ex (sp),hl ;bc = len, hl=offs push de ex de,hl ex af,af' ld a,4 cp d jr nc,apskip2 inc bc or a apskip2: ld hl,127 sbc hl,de jr c,apskip3 inc bc inc bc apskip3: pop hl ;bc = len, de = offs, hl=junk push hl or a sbc hl,de ex af,af' pop de ;hl=dest-offs, bc=len, de = dest ldir pop hl ld ixh,b jp aploop ap_r0_gamma: call ap_getgamma2 ;and a new gamma code for length push hl push de ex de,hl ld d,iyh ld e,iyl sbc hl,de pop de ;hl=dest-offs, bc=len, de = dest ldir pop hl ld ixh,b jp aploop ap_getgamma2: ex af,af' ap_getgamma: ld bc,1 add a,a jr nz,apnogetbit5 ld a,(hl) inc hl rla apnogetbit5: rl c add a,a jr nz,apnogetbit6 ld a,(hl) inc hl rla apnogetbit6: ret nc add a,a jr nz,apnogetbit7 ld a,(hl) inc hl rla apnogetbit7: rl c add a,a jr nz,apnogetbit8 ld a,(hl) inc hl rla apnogetbit8: ret nc ap_getgammaloop:add a,a jr nz,apnogetbit9 ld a,(hl) inc hl rla apnogetbit9: rl c rl b add a,a jr nz,apnogetbit10 ld a,(hl) inc hl rla apnogetbit10: jr c,ap_getgammaloop ret Y por último una idea de Antonio Villena, gastando todavía más bytes, para favorecer el caso más común (247 bytes, 2 bits optimizados como en la anterior): Código: ; aPPack decompressor ; original source by dwedit ; very slightly adapted by utopian ; optimized by Metalbrain & Antonio Villena ;hl = source ;de = dest depack: ld a,128 apbranch1: ldi aploop2: ld ixh,1 aploop: add a,a jr nz,apnogetbit1 ld a,(hl) inc hl rla apnogetbit1: jr nc,apbranch1 add a,a jr nz,apnogetbit2 ld a,(hl) inc hl rla apnogetbit2: jr nc,apbranch2 add a,a jr nz,apnogetbit3 ld a,(hl) inc hl rla apnogetbit3: jr nc,apbranch3 ld bc,16 ;get an offset apget4bits: add a,a jr nz,apnogetbit4 ld a,(hl) inc hl rla apnogetbit4: rl c jr nc,apget4bits jr nz,apbranch4 ex de,hl ld (hl),b ;write a 0 ex de,hl inc de jp aploop2 apbranch4: ex af,af' ex de,hl ;write a previous byte (1-15 away from dest) sbc hl,bc ld a,(hl) add hl,bc ld (hl),a ex af,af' ex de,hl inc de jp aploop2 apbranch3: ld c,(hl) ;use 7 bit offset, length = 2 or 3 inc hl ex af,af' rr c ret z ;if a zero is found here, it's EOF ld a,2 ld b,0 adc a,b push hl ld iyh,b ld iyl,c ld h,d ld l,e sbc hl,bc ld c,a ex af,af' ldir pop hl ld ixh,b jp aploop apbranch2: call ap_getgamma ;use a gamma code * 256 for offset, another gamma code for length dec c ex af,af' ld a,c sub ixh jr z,ap_r0_gamma dec a ;do I even need this code? ;bc=bc*256+(hl), lazy 16bit way ld b,a ld c,(hl) inc hl ld iyh,b ld iyl,c push bc call ap_getgamma2 ex (sp),hl ;bc = len, hl=offs push de ex de,hl ex af,af' ld a,4 cp d jr nc,apskip2 inc bc or a apskip2: ld hl,127 sbc hl,de jr c,apskip3 inc bc inc bc apskip3: pop hl ;bc = len, de = offs, hl=junk push hl or a sbc hl,de ex af,af' pop de ;hl=dest-offs, bc=len, de = dest ldir pop hl ld ixh,b jp aploop ap_r0_gamma: call ap_getgamma2 ;and a new gamma code for length push hl push de ex de,hl ld d,iyh ld e,iyl sbc hl,de pop de ;hl=dest-offs, bc=len, de = dest ldir pop hl ld ixh,b jp aploop ap5: ld a,(hl) inc hl rla jp apnogetbit5 ap6: ld a, (hl) inc hl rla jp apnogetbit6 ap7: ld a, (hl) inc hl rla jp apnogetbit7 ap8: ld a, (hl) inc hl rla jp apnogetbit8 ap9: ld a, (hl) inc hl rla jp apnogetbit9 ap10: ld a, (hl) inc hl rla ret nc jp ap_getgammaloop ap_getgamma2: ex af, af' ap_getgamma: ld bc, 1 add a, a jr z, ap5 apnogetbit5: rl c add a, a jr z, ap6 apnogetbit6: ret nc add a, a jr z, ap7 apnogetbit7: rl c add a, a jr z, ap8 apnogetbit8: ret nc ap_getgammaloop:add a, a jr z, ap9 apnogetbit9: rl c rl b add a, a jr z, ap10 apnogetbit10: ret nc jp ap_getgammaloop Título: Re: aPLib, rutinas optimizadas Publicado por: j4mk3 en 29 de Enero de 2013, 01:13:04 am Suuper interesante para ese concurso que yo me se de 16K ROM :)
Me lo estudiaré a ver si puedo entenderlo y usarlo. Muchas gracias por el codigo. Título: Re: aPLib, rutinas optimizadas Publicado por: kabish en 29 de Enero de 2013, 11:01:57 pm Gracias por todo tu curro. :police:
|