git.sur5r.net Git - cc65/blob - libsrc/common/lz4.s

   1 ;
   2 ; Lauri Kasanen, 6 Jun 2017
   3 ; (C) Mega Cat Studios
   4 ; An optimized LZ4 decompressor
   5 ;
   6 ; Almost 7 times faster, uses no RAM (vs 14 bytes BSS), and takes 1/4 the space
   7 ; vs the official C source.
   8 ;
   9
  10         .importzp       sp, sreg, regsave, regbank
  11         .importzp       tmp1, tmp2, tmp3, tmp4, ptr1, ptr2, ptr3, ptr4
  12         .macpack        longbranch
  13         .import         memcpy_upwards,pushax,popax
  14         .export         _decompress_lz4
  15
  16 out = regsave
  17 written = regsave + 2
  18 tmp = tmp1
  19 token = tmp2
  20 offset = ptr3
  21 in = sreg
  22 outlen = ptr4
  23
  24 ; ---------------------------------------------------------------
  25 ; void decompress_lz4 (const u8 *in, u8 * const out, const u16 outlen)
  26 ; ---------------------------------------------------------------
  27
  28 .segment        "CODE"
  29
  30 .proc   _decompress_lz4: near
  31
  32         sta     outlen
  33         stx     outlen+1
  34
  35         jsr     popax
  36         sta     out
  37         stx     out+1
  38
  39         jsr     popax
  40         sta     in
  41         stx     in+1
  42
  43 ;
  44 ; written = 0;
  45 ;
  46         lda     #$00
  47         sta     written
  48 ;
  49 ; while (written < outlen) {
  50 ;
  51         jmp     L0046
  52 ;
  53 ; token = *in++;
  54 ;
  55 L0004:  ldy     #$00
  56         lda     (in),y
  57         sta     token
  58
  59         inc     in
  60         bne     L000A
  61         inc     in+1
  62 L000A:
  63 ;
  64 ; offset = token >> 4;
  65 ;
  66         ldx     #$00
  67         lsr     a
  68         lsr     a
  69         lsr     a
  70         lsr     a
  71         sta     offset
  72         stx     offset+1
  73 ;
  74 ; token &= 0xf;
  75 ; token += 4; // Minmatch
  76 ;
  77         lda     token
  78         and     #$0F
  79         clc
  80         adc     #$04
  81         sta     token
  82 ;
  83 ; if (offset == 15) {
  84 ;
  85         lda     offset
  86         cmp     #$0F
  87 L0013:  bne     L001A
  88 ;
  89 ; tmp = *in++;
  90 ;
  91         ldy     #$00
  92         lda     (in),y
  93         sta     tmp
  94
  95         inc     in
  96         bne     L0017
  97         inc     in+1
  98 L0017:
  99 ;
 100 ; offset += tmp;
 101 ;
 102         clc
 103         adc     offset
 104         sta     offset
 105         lda     #$00
 106         adc     offset+1
 107         sta     offset+1
 108 ;
 109 ; if (tmp == 255)
 110 ;
 111         lda     tmp
 112         cmp     #$FF
 113 ;
 114 ; goto moreliterals;
 115 ;
 116         jmp     L0013
 117 ;
 118 ; if (offset) {
 119 ;
 120 L001A:  lda     offset
 121         ora     offset+1
 122         beq     L001C
 123 ;
 124 ; memcpy(&out[written], in, offset);
 125 ;
 126         lda     out
 127         clc
 128         adc     written
 129         sta     ptr2
 130         lda     out+1
 131         adc     written+1
 132         tax
 133         lda     ptr2
 134         stx     ptr2+1
 135         jsr     pushax
 136         lda     in
 137         ldx     in+1
 138         sta     ptr1
 139         stx     ptr1+1
 140         ldy     #$00
 141         jsr     memcpy_upwards
 142 ;
 143 ; written += offset;
 144 ;
 145         lda     offset
 146         clc
 147         adc     written
 148         sta     written
 149         lda     offset+1
 150         adc     written+1
 151         sta     written+1
 152 ;
 153 ; in += offset;
 154 ;
 155         lda     offset
 156         clc
 157         adc     in
 158         sta     in
 159         lda     offset+1
 160         adc     in+1
 161         sta     in+1
 162 ;
 163 ; if (written >= outlen)
 164 ;
 165 L001C:  lda     written
 166         cmp     outlen
 167         lda     written+1
 168         sbc     outlen+1
 169 ;
 170 ; return;
 171 ;
 172         bcc     L0047
 173         rts
 174 ;
 175 ; memcpy(&offset, in, 2);
 176 ;
 177 L0047:  ldy     #$00
 178         lda     (in),y
 179         sta     offset
 180         iny
 181         lda     (in),y
 182         sta     offset+1
 183 ;
 184 ; in += 2;
 185 ;
 186         lda     #$02
 187         clc
 188         adc     in
 189         sta     in
 190         bcc     L002F
 191         inc     in+1
 192 ;
 193 ; copysrc = out + written - offset;
 194 ;
 195 L002F:  lda     out
 196         clc
 197         adc     written
 198         pha
 199         lda     out+1
 200         adc     written+1
 201         tax
 202         pla
 203         sec
 204         sbc     offset
 205         sta     ptr1
 206         txa
 207         sbc     offset+1
 208         sta     ptr1+1
 209 ;
 210 ; offset = token;
 211 ;
 212         lda     #$00
 213         sta     offset+1
 214         lda     token
 215         sta     offset
 216 ;
 217 ; if (token == 19) {
 218 ;
 219         cmp     #$13
 220 L0045:  bne     L003C
 221 ;
 222 ; tmp = *in++;
 223 ;
 224         ldy     #$00
 225         lda     (in),y
 226         sta     tmp
 227
 228         inc     in
 229         bne     L0039
 230         inc     in+1
 231 L0039:
 232 ;
 233 ; offset += tmp;
 234 ;
 235         clc
 236         adc     offset
 237         sta     offset
 238         tya
 239         adc     offset+1
 240         sta     offset+1
 241 ;
 242 ; if (tmp == 255)
 243 ;
 244         lda     tmp
 245         cmp     #$FF
 246 ;
 247 ; goto morematches;
 248 ;
 249         jmp     L0045
 250 ;
 251 ; memcpy(&out[written], copysrc, offset);
 252 ;
 253 L003C:  lda     out
 254         clc
 255         adc     written
 256         sta     ptr2
 257         lda     out+1
 258         adc     written+1
 259         tax
 260         lda     ptr2
 261         stx     ptr2+1
 262         jsr     pushax
 263         jsr     memcpy_upwards
 264 ;
 265 ; written += offset;
 266 ;
 267         lda     offset
 268         clc
 269         adc     written
 270         sta     written
 271         lda     offset+1
 272         adc     written+1
 273 L0046:  sta     written+1
 274 ;
 275 ; while (written < outlen) {
 276 ;
 277         lda     written
 278         cmp     outlen
 279         lda     written+1
 280         sbc     outlen+1
 281         jcc     L0004
 282
 283         rts
 284
 285 .endproc
 286