packing data with variable length

artrag · February 4, 2021

I am interested in developing (in intybasic) a general purpose subroutine able to extract a code with a given number of bits from a bitstream of words stored as DATA

Something close to this:

#bitstream:

DATA &1001100110011001,&1001100110011001,&1001100110011001,&1001100110011001,&1001100110011001,.....

read_code: procedure

' input: n number of bits to read (from 1 to 16)

' output: #code value of the n bits extracted from the stream

' local variables: #bit_index - starts from 0 and each time you read a code is incremented of n, "pointing" to the current next bit to be extracted

' local constant: #max_bit_index - used to testing against overflow, you cannot read after the end of the bitstream

[do the magic]

end

Does anyone have such a routine already developed and tested and wants to share it?

+DZ-Jay · February 4, 2021

Are the bits to be read at predictable boundaries? I mean, are they packed bytes or smaller words, or just a ragged stream of fields of variable and unpredictable length ("extract n bits starting at m position")?

Edited February 4, 2021 by DZ-Jay

artrag · February 4, 2021

The idea is to have a tool able to extract n bits from the current position and to update the current position.

As you know from other threads we need to read a variable number of bits from 3 to 14 bits each time.

Edited February 4, 2021 by artrag
typos

+DZ-Jay · February 4, 2021

14 minutes ago, artrag said:

The idea is to have a tool able to extract n bits from the current position and to update the current position.

Gotcha!

14 minutes ago, artrag said:

As you know from other threads we need to read a variable number of bits from 3 to 14 bits each time.

Sorry, I wasn't sure which solution you were trying.

I'll see what I can come up with, but @intvnut and @nanochess probably have already solved this before in IntyBASIC.

-dZ.

artrag · February 7, 2021

No proposal?

+DZ-Jay · February 7, 2021

5 hours ago, artrag said:

No proposal?

Sorry, I haven't had a chance to complete it. I'm trying to improve it since I'm not that good in IntyBASIC and my initial draft was an ugly hog. I'll post something later today for review.

+DZ-Jay · February 7, 2021

NOTE (15-Feb-2021):

This post has been updated to correct various errors in the description of the algorithm, and in the source code for the reference implementation. When originally posted, in a rush to get something out quickly, I had not actually tested the code, and the documentation still reflected an older approach that relied on a Little Endian data format. I have reviewed and tested everything now to ensure it works as intended.

Also, the source code includes a few optimizations to avoid relying on arbitrary multiplication and division, which is very slow. I'm sure further optimizations are still possible to reduce memory access of variables.

The reference implementation includes only the BACKTAB command decoder and the field extraction functions. The implementation of the encoder is left to the user, for it is not bound to IntyBASIC or any other specific language.

OK, so here's what I have. I haven't tested it fully yet, so it may have bugs -- and of course, it may not be the best IntyBASIC code ever (it's kind of hard to translate elegant bit-wrangling operations on registers, to cumbersome IntyBASIC arithmetic expressions).

Here is a sample implementation of an "unpack" algorithm for compressing BACKTAB data in FG/BG mode.

I took the liberty of splitting the original problem statement we discussed into two individual problems, described below. I offer solutions to both, but the second is the important one, the one you actually asked for here.

How to draw a scene on BACKTAB where the data words are encoded as a series of drawing commands and stored in a bitstream dataset.
How to extract the next bitfield of an arbitrary length from a bitstream dataset.

Like I said, you asked only for the second one, but I provide a practical holistic solution for your consideration, which includes a specialized encoding scheme. If you want to use your own encoding scheme, then you can ignore the entire first part and focus on the bitfield extraction.

First, a few assumptions and description of the encoding scheme (Problem #1)

A BACKTAB word is composed of three attribute fields
- FG Color
- BG Color
- Picture card index
The encoding scheme defines a series of "drawing instructions," which I call "commands," representing the attribute changes.
Each command is a bitfield composed of three parts:
- 2 Bits: Command code
- 1 Bit: BACKTAB update flag
- 3 to 6 Bits: Command argument
Because the length of the command argument varies, the whole command word can be 6 to 9 bits long.
All command words are packed into 16-bit data, in Big Endian format, so that the bitstream can be read from left to right.

Command Word:

COMMAND WORD:
=============

+---+---+---+---+---+---+---+---+---+
| U | C | C | A | A | A | A | A | A |
+---+---+---+---+---+---+---+---+---+
  8   7   6   5   4   3   2   1   0  

LEGEND:
=======
  U  BACKTAB Update Flag
  C  Command Code
  A  Argument

Command Codes:

01: Set FG Color
Argument: FG Color (3 Bits)
Format: CCC
10: Set BG Color
Argument: BG Color (5 Bits)
Format: CC0CC
The format is the same as expected by the BACKTAB in FG/BG mode.
11: Set Picture Card
Argument: Card Index (7 Bits)
Format: FPPPPPP
The least significant bits are the card index, the most significant bit is the GRAM flag: 0 = GROM card; 1 = GRAM card.
00: Continue (No Change)
Argument: Run Length (4 Bits)
Format: LLLL
The length is how many times the current word will be repeated in BACKTAB until the next drawing command.

Update BACKTAB Flag:

All commands are applied in series to the last known BACKTAB word used. When multiple commands must be applied for the same word, they will be processed in sequence, and the last one indicates that the word is ready for posting by setting the "Update BACKTAB" flag.

0 = Do not update BACKTAB, word still incomplete

1 = Word is complete, updated BACKTAB

Below is the full code for your consideration, which remains untested. The procedure ProcessNextCommand() represents the solution to problem #1: it decodes the next command and composes the BACKTAB word as necessary. The procedure ExtractBitField() represents the solution to problem #2, and is independent of the encoding scheme: it extracts the next field of a given length from the bitstream, updating an internal buffer from ROM as necessary.

The only shared assumption between the two procedures is that the fields are packed in Big Endian format, meaning that the first field appears in the most significant bits of a 16-bit word in ROM:

PACKED DATA:
============

 ,_____________________ First Data Word _______________________,     ,_____________________ Second Data Word ______________________,
/                                                               \   /                                                               \
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+   +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| X | X | X | X | X | X | Y | Y | Y | Y | Y | Y | Y | Z | Z | Z |   | Z | Z | Z | Z | Z | Z | W | W | W | W | W | W | . | . | . | . |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+   +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
  F   E   D   C   B   A   9   8   7   6   5   4   3   2   1   0       F   E   D   C   B   A   9   8   7   6   5   4   3   2   1   0  
\______________________/\__________________________/\______________________________________/\______________________/
     Command Word #1          Command Word #2                   Command Word #3                  Command Word #4
      (Length = 6)             (Length = 7)                      (Length = 9)                     (Length = 6)

    DATA <First Data Word>, <Second Data Word>, ...

Below is the code to the reference implementation. I've also attached a copy of the module I wrote.

Spoiler


' =========================================================================
' BACKTAB Unpack Reference Implementation
' -------------------------------------------------------------------------
'     Programmer: DZ-Jay
'     Created:    2021-02-05
'     Updated:    2021-02-15
' =========================================================================

' Constants
' -----------------------------------------------
Const MSK_CMD           = &0000000000000111
Const MSK_CMD_POST_FLG  = &0000000000000100
Const MSK_CMDARG_0      = &0000000000001111
Const MSK_CMDARG_1      = &0000000000000111
Const MSK_CMDARG_2      = &0000000000011011
Const MSK_CMDARG_3      = &0000000000111111
Const MSK_CMDARG_GRAM   = &0000000000100000

Const MSK_BTAB_FG_COL   = &0000000000000111
Const MSK_BTAB_BG_COL   = &0011011000000000
Const MSK_BTAB_PIC      = &0000100111111000

Const MSK_GRAM_FLG      = &0000100000000000
Const BUFFER_OFFS_EMTPY = 16
Const BUFFER_OFFS_FULL  = 0
Const NULL              = 0

' Macros
' -----------------------------------------------
DEF FN Pow2(Exp)            = Pow2Table(Exp)
DEF FN Pow2Mask(Exp)        = (Pow2(Exp) - 1)
DEF FN ExtractField(Bits)   = FieldLen = Bits : Gosub ExtractBitField
DEF FN ShiftLeft(Val, Bits) = #Temp0 = Val : #Temp1 = Bits : Gosub ShiftBitsLeft
DEF FN ShiftRight(Val, Bits)= #Temp0 = Val : #Temp1 = Bits : Gosub ShiftBitsRight

' Variables
' -----------------------------------------------
    Dim UpdateFlg
    Dim Offset
    Dim FieldLen
    Dim Skip
    Dim #Temp0
    Dim #Temp1
    Dim #Field
    Dim #Buffer
    Dim #Output

    Offset  = BUFFER_OFFS_EMTPY
    #Buffer = 0
    #Output = 0

' ProcessNextCommand:
'   Input:
'       Idx         - Current BACKTAB index
'       Skip        - Skip counter for RLE
'       #Output     - Last BACKTAB word
'
'   Output:
'       Skip        - Updated skip counter
'       #Output     - Updated BACKTAB word
'       UpdateFlg   - Update BACKTAB flag
'
'   COMMAND WORD FORMAT:
'       +---+---+---+---+---+---+---+---+---+
'       | U | C | C | A | A | A | A | A | A |
'       +---+---+---+---+---+---+---+---+---+
'         8   7   6   5   4   3   2   1   0
'
'   LEGEND:
'       C  Command Code
'       U  BACKTAB Update Flag
'       A  Argument
' -----------------------------------------------
ProcessNextCommand: Procedure
    If (Skip > 0) Then
        Skip      = (Skip - 1)
        UpdateFlg = 1
    Else

        ' Get command field
        ExtractField(3)  ' #Field = ExtractBitField(3)

        UpdateFlg = (#Field And MSK_CMD_POST_FLG)

        ' Command #3: Set Picture (6b: &111111)
        If (#Field > 6) Then
            ' Get Picture argument
            ExtractField(6)     ' #Field = ExtractBitField(6)

            ' Propagate GRAM flag
            If (#Field And MSK_CMDARG_GRAM) Then
                #Field = (MSK_GRAM_FLG + (#Field Xor MSK_CMDARG_GRAM))
            End If

            #Output = ((#Output And MSK_BTAB_PIC) + #Field)

        ' Command #2: Set BG Color (5b: &11011)
        ElseIf (#Field > 4) Then
            ' Get BG Color argument
            ExtractField(5)     ' #Field = ExtractBitField(5)
            #Output = ((#Output And MSK_BTAB_BG_COL) + #Field)

        ' Command #1: Set FG Color (3b: &111)
        ElseIf (#Field > 2) Then
            ' Get FG Color argument
            ExtractField(3)     ' #Field = ExtractBitField(3)
            #Output = ((#Output And MSK_BTAB_FG_COL) + #Field)

        ' Command #0: Continue (4b: &1111)
        Else
            ' Get Skip (Run Length) argument
            ExtractField(4)     ' #Field = ExtractBitField(4)
            Skip = (#Field And $FF)

        End If
    End If

    Return
End

' ExtractBitField
'   Input:
'     FieldLen    - The length of the bitfield to read
'     Offset      - The current offset within the buffer
'     #Buffer     - The last packed word read
'
'   Output:
'     Offset      - New buffer offset position
'     #Field      - The next bitfield of FieldLen requested
'
'   Trashed:
'     FieldLen    - Potentialy altered during processing
ExtractBitField: Procedure
    ' If there aren't enough bits left in the buffer,
    ' take those first, then force to read a new word
    ' into the buffer for the rest.
    If (FieldLen > Offset) Then
        FieldLen = (FieldLen - Offset)

        ' Get whatever is left from the current buffer
        ' and shift the bits into position, to open
        ' space for the missing ones.
        '
        ' We do not need to shift the mask because we
        ' assume that the field is in the LSBs.
        ShiftLeft((#Buffer And Pow2Mask(Offset)), FieldLen)
        #Field   = #Temp0
        Offset   = BUFFER_OFFS_EMTPY
    Else
        #Field   = NULL
    End If

    ' Read another word if we've exhausted the buffer.
    If (Offset = BUFFER_OFFS_EMTPY) Then
        Read #Buffer
    End If

    ' Compose field value and update buffer offset
    Offset = (Offset - FieldLen)
    ShiftRight(#Buffer, Offset)

    ' By masking the field after shifting, we avoid
    ' having to align the mask.  We then mask always
    ' starting at the LSB.
    #Field  = (#Field + (#Temp0 And Pow2Mask(FieldLen)))
    Return
End

' ShiftBitsLeft
'   Input:
'     #Temp0    - Value to shift left
'     #Temp1    - Number of bits to shift left
'
'   Output:
'     #Temp0    - Shifted value
ShiftBitsLeft: Procedure
    On #Temp1 Fast GoTo \
        .extract_00, .extract_01, .extract_02, .extract_03, \
        .extract_04, .extract_05, .extract_06, .extract_07, \
        .extract_08, .extract_09, .extract_10, .extract_11, \
        .extract_12, .extract_13, .extract_14, .extract_15

    ' Select Case (#Temp1)
    .extract_00:
        ' #Temp0 = (#Temp0 * 1)           ' × 2^0 = 1  <-- Yeah, we skip this one!
        Return

    .extract_01:
        #Temp0 = (#Temp0 * 2)           ' × 2^1 = 2
        Return

    .extract_02:
        #Temp0 = (#Temp0 * 4)           ' × 2^2 = 4
        Return

    .extract_03:
        #Temp0 = (#Temp0 * 8)           ' × 2^3 = 8
        Return

    .extract_04:
        #Temp0 = (#Temp0 * 16)          ' × 2^4 = 16
        Return

    .extract_05:
        #Temp0 = (#Temp0 * 32)          ' × 2^5 = 32
        Return

    .extract_06:
        #Temp0 = (#Temp0 * 64)          ' × 2^6 = 64
        Return

    .extract_07:
        #Temp0 = (#Temp0 * 128)         ' × 2^7 = 128
        Return

    .extract_08:
        #Temp0 = (#Temp0 * 256)         ' × 2^8 = 256
        Return

    .extract_09:
        #Temp0 = (#Temp0 * 256 * 2)     ' × 2^9 = 512
        Return

    .extract_10:
        #Temp0 = (#Temp0 * 256 * 4)     ' × 2^10 = 1,024
        Return

    .extract_11:
        #Temp0 = (#Temp0 * 256 * 8)     ' × 2^11 = 2,048
        Return

    .extract_12:
        #Temp0 = (#Temp0 * 256 * 16)    ' × 2^12 = 4,096
        Return

    .extract_13:
        #Temp0 = (#Temp0 * 256 * 32)    ' × 2^13 = 8,192
        Return

    .extract_14:
        #Temp0 = (#Temp0 * 256 * 64)    ' × 2^14 = 16,384
        Return

    .extract_15:
        #Temp0 = (#Temp0 * 256 * 128)   ' × 2^15 = 32,768
        Return
End

' ShiftBitsRight
'   Input:
'     #Temp0    - Value to shift right
'     #Temp1    - Number of bits to shift right
'
'   Output:
'     #Temp0    - Shifted value
ShiftBitsRight: Procedure
    On #Temp1 Fast GoTo \
        .extract_00, .extract_01, .extract_02, .extract_03, \
        .extract_04, .extract_05, .extract_06, .extract_07, \
        .extract_08, .extract_09, .extract_10, .extract_11, \
        .extract_12, .extract_13, .extract_14, .extract_15

    ' Select Case (#Temp1)
    .extract_00:
        ' #Temp0 = (#Temp0 / 1)           ' ÷ 2^0 = 1  <-- Yeah, we skip this one!
        Return

    .extract_01:
        #Temp0 = (#Temp0 / 2)           ' ÷ 2^1 = 2
        Return

    .extract_02:
        #Temp0 = (#Temp0 / 4)           ' ÷ 2^2 = 4
        Return

    .extract_03:
        #Temp0 = (#Temp0 / 8)           ' ÷ 2^3 = 8
        Return

    .extract_04:
        #Temp0 = (#Temp0 / 16)          ' ÷ 2^4 = 16
        Return

    .extract_05:
        #Temp0 = (#Temp0 / 32)          ' ÷ 2^5 = 32
        Return

    .extract_06:
        #Temp0 = (#Temp0 / 64)          ' ÷ 2^6 = 64
        Return

    .extract_07:
        #Temp0 = (#Temp0 / 128)         ' ÷ 2^7 = 128
        Return

    .extract_08:
        #Temp0 = (#Temp0 / 256)         ' ÷ 2^8 = 256
        Return

    .extract_09:
        #Temp0 = (#Temp0 / 256 / 2)     ' ÷ 2^9 = 512
        Return

    .extract_10:
        #Temp0 = (#Temp0 / 256 / 4)     ' ÷ 2^10 = 1,024
        Return

    .extract_11:
        #Temp0 = (#Temp0 / 256 / 8)     ' ÷ 2^11 = 2,048
        Return

    .extract_12:
        #Temp0 = (#Temp0 / 256 / 16)    ' ÷ 2^12 = 4,096
        Return

    .extract_13:
        #Temp0 = (#Temp0 / 256 / 32)    ' ÷ 2^13 = 8,192
        Return

    .extract_14:
        #Temp0 = (#Temp0 / 256 / 64)    ' ÷ 2^14 = 16,384
        Return

    .extract_15:
        #Temp0 = (#Temp0 / 256 / 128)   ' ÷ 2^15 = 32,768
        Return
End

' Data Tables
' -----------------------------------------------

    ' Table of Powers of 2 (0..15)
Pow2Table:
    DATA    $0001, $0002, $0004, $0008, $0010, $0020, $0040, $0080
    DATA    $0100, $0200, $0400, $0800, $1000, $2000, $4000, $8000

I have tested the above reference implementation and it works. Notwithstanding, feedback or corrections are welcomed.

Download the code below:

pkscn.bas - IntyBASIC SDK Sample Project
unpack.bas - Un-Pack Reference Implementation Module

Edited February 15, 2021 by DZ-Jay
Updated to fix errors

+DZ-Jay · February 7, 2021

Sorry, had a copy+paste error in one line when I tried to rename a constant for the sake of clarity -- and of course, I forgot to compile first to make sure I did it right. Oops!

If you downloaded it before this comment, get it again.

Edited February 7, 2021 by DZ-Jay

artrag · February 7, 2021

Thanks for the elegant solution!

I wasn't asking that much ;-)

+DZ-Jay · February 7, 2021

17 minutes ago, artrag said:

Thanks for the elegant solution!

Don't thank me yet until you test it. It works in my head, and it compiles. That's as far as I got.

Quote

I wasn't asking that much

No worries, I didn't think you were. It was a fun puzzle to solve. :)

By the way, the idea of encoding BACKTAB data as drawing commands came from @Arnauld. He brought it up in a different discussion, but I can't recall where or when. I used something similar (but more crude) in the past once, but it's been a while. Also, it was in Assembly Language, where bit-wrangling is sort of a given.

All that said, even if it works, there may be ways to exploit the language to have the compiler generate more optimal assembly code. I admit that I haven't dug too deep into the compiler's inner workings. Perhaps @intvnut or @nanochess can chime in and offer alternatives or suggestions.

-dZ.

Edited February 7, 2021 by DZ-Jay

+nanochess · February 8, 2021

I read the post and I have it in my list of pending posts to answer, but I've been too busy. DZ did a good solution.

+DZ-Jay · February 8, 2021

@artrag,

Another idea that came to mind, which may not work for your purposes, is of drawing each GRAM card in a buffer algorithmically. The EXEC has such a feature, where it encodes the entirety of an 8-byte GRAM card as drawing instructions in a 16-bit bitmap. That's four DECLEs compacted into one.

Of course, the practical algorithms available limit the graphical expression of the card to geometric shapes, and simple lines and fills, but I would wager that a great number of cards in your backgrounds are of such kind.

You could mix-and-match both mechanisms, somehow encoding in your BACKTAB data whether it's a "predefined" GRAM card in ROM, or a "generated" GRAM card; then call a different loading routine for each.

All this complicates the program and the graphics loader, so I would only recommend it if you run out of ROM and absolutely need to cram more graphics in, and the other compression methods are exhausted.

In my opinion, if it really came to that, you're better off limiting the number of scenes for the IntyBASIC contest, then go "full hog" on a later cart release using optimized assembly code and bank-switching.

I'd just thought to bring it up because it was a clever solution that Mattel programmers came up with to work-around their excruciatingly tight ROM constraints.

-dZ.

Edited February 8, 2021 by DZ-Jay

artrag · February 12, 2021

On 2/7/2021 at 1:20 PM, DZ-Jay said:
OK, so here's what I have. I haven't tested it fully yet, so it may have bugs -- and of course, it may not be the best IntyBASIC code ever (it's kind of hard to translate elegant bit-wrangling operations on registers, to cumbersome IntyBASIC arithmetic expressions).

I took the liberty of splitting the original problem statement we discussed into two individual problems, described below. I offer solutions to both, but the second is the important one, the one you actually asked for here.

How to draw a scene on BACKTAB where the data words are encoded as a series of drawing commands and stored in a bitstream dataset.

How to extract the next bitfield of an arbitrary length from a bitstream dataset.

Like I said, you asked only for the second one, but I provide a practical holistic solution for your consideration, which includes a specialized encoding scheme. If you want to use your own encoding scheme, then you can ignore the entire first part and focus on the bitfield extraction.

First, a few assumptions and description of the encoding scheme (Problem #1)

A BACKTAB word is composed of three attribute fields

FG Color

BG Color

Picture card index

The encoding scheme defines a series of "drawing instructions," which I call "commands," representing the attribute changes.

Each command is a bitfield composed of three parts:

2 Bits: Command code

1 Bit: BACKTAB update flag

3 to 6 Bits: Command argument

Because the length of the command argument varies, the whole command word can be 6 to 9 bits long.

All command words are packed into 16-bit data, in Big Endian format, so that the bitstream can be read from left to right.

Command Word:
COMMAND WORD:
=============

+---+---+---+---+---+---+---+---+---+
| A | A | A | A | A | A | U | C | C |
+---+---+---+---+---+---+---+---+---+
  8   7   6   5   4   3   2   1   0  

LEGEND:
=======
  C  Command Code
  U  BACKTAB Update Flag
  A  Argument
Command Codes:

01: Set FG Color
Argument: FG Color (3 Bits)
Format: CCC

10: Set BG Color
Argument: BG Color (5 Bits)
Format: CC0CC
The format is the same as expected by the BACKTAB in FG/BG mode.

11: Set Picture Card
Argument: Card Index (6 Bits)
Format: FPPPPP
The least significant bits are the card index, the most significant bit is the GRAM flag: 0 = GROM card; 1 = GRAM card.

00: Continue (No Change)
Argument: Run Length (4 Bits)
Format: LLLL
The length is how many times the current word will be repeated in BACKTAB until the next drawing command.

Update BACKTAB Flag:

All commands are applied in series to the last known BACKTAB word used. When multiple commands must be applied for the same word, they will be processed in sequence, and the last one indicates that the word is ready for posting by setting the "Update BACKTAB" flag.

0 = Do not update BACKTAB, word still incomplete

1 = Word is complete, updated BACKTAB

Below is the full code for your consideration, which remains untested. The procedure ProcessNextCommand() represents the solution to problem #1: it decodes the next command and composes the BACKTAB word as necessary. The procedure ExtractBitField() represents the solution to problem #2, and is independent of the encoding scheme: it extracts the next field of a given length from the bitstream, updating an internal buffer from ROM as necessary.

The only shared assumption between the two procedures is that the fields are packed in Big Endian format, meaning that the first field appears in the most significant bits of a 16-bit word in ROM:
PACKED DATA:
============

 ,_____________________ First Data Word _______________________,     ,_____________________ Second Data Word ______________________,
/                                                               \   /                                                               \
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+   +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| X | X | X | X | X | X | Y | Y | Y | Y | Y | Y | Y | Z | Z | Z |   | Z | Z | Z | Z | Z | Z | W | W | W | W | W | W | . | . | . | . |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+   +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
  F   E   D   C   B   A   9   8   7   6   5   4   3   2   1   0       F   E   D   C   B   A   9   8   7   6   5   4   3   2   1   0  
\______________________/\__________________________/\______________________________________/\______________________/
     Command Word #1          Command Word #2                   Command Word #3                  Command Word #4
      (Length = 6)             (Length = 7)                      (Length = 9)                     (Length = 6)

    DATA <First Data Word>, <Second Data Word>, ...
Below is the code to the reference implementation. I've also attached a copy of the module I wrote.
Reveal hidden contents
' Constants
' -----------------------------------------------
Const MSK_CMD           = &0000000000000111
Const MSK_CMD_POST_FLG  = &0000000000000100
Const MSK_CMDARG_0      = &0000000000001111
Const MSK_CMDARG_1      = &0000000000000111
Const MSK_CMDARG_2      = &0000000000011011
Const MSK_CMDARG_3      = &0000000000111111
Const MSK_CMDARG_GRAM   = &0000000000100000

Const MSK_BTAB_FG_COL   = &0000000000000111
Const MSK_BTAB_BG_COL   = &0011011000000000
Const MSK_BTAB_PIC      = &0000100111111000

Const MSK_GRAM_FLG      = &0000100000000000

' Macros
' -----------------------------------------------
DEF FN Pow2(Exp)            = (VarPtr Pow2Table(Exp))
DEF FN Pow2Mask(Exp)        = ((VarPtr Pow2Table(Exp)) - 1)
DEF FN ExtractField(Bits)   = FieldLen = Bits : Gosub ExtractBitField

' Variables
' -----------------------------------------------
Dim Idx
Dim UpdateFlg
Dim Temp
Dim Offset
Dim FieldLen
Dim Skip
Dim #Field
Dim #Buffer
Dim #Output


' Initialize
' -----------------------------------------------
    Idx         = 0
    Offset      = 0
    Skip        = 0
    #Buffer     = 0
    #Output     = 0

' Draw Scene
' -----------------------------------------------
    Do
        Gosub ProcessNextCommand
        If (UpdateFlg) Then
            #BACKTAB(Idx) = #Output
            Idx = (Idx + 1)
        End If
    Loop Until (Idx > 239)


' ProcessNextCommand:
'   Input:
'       Idx         - Current BACKTAB index
'       Skip        - Skip counter for RLE
'       #Output     - Last BACKTAB word
'
'   Output:
'       Skip        - Updated skip counter
'       #Output     - Updated BACKTAB word
'       UpdateFlg   - Update BACKTAB flag
'
'   Trashed:
'       Temp        - Used for temporary values
' -----------------------------------------------
ProcessNextCommand: Procedure
    If (Skip > 0) Then
        Skip      = (Skip - 1)
        UpdateFlg = 1
    Else
        ' Get command field
        ExtractField(3)  ' #Field = ExtractBitField(3)

        UpdateFlg = (#Field And MSK_CMD_POST_FLG)

        ' Command #3: Set Picture (6b: &111111)
        If (#Field > 6) Then
            ' Get Picture argument
            ExtractField(6)     ' #Field = ExtractBitField(6)

            ' Propagate GRAM flag
            If (#Field And MSK_CMDARG_GRAM) Then
                #Field = (MSK_GRAM_FLG + (#Field Xor MSK_CMDARG_GRAM))
            End If

            #Output = ((#Output And MSK_BTAB_PIC) + #Field)

        ' Command #2: Set BG Color (5b: &11011)
        ElseIf (#Field > 4) Then
            ' Get BG Color argument
            ExtractField(5)     ' #Field = ExtractBitField(5)
            #Output = ((#Output And MSK_BTAB_BG_COL) + #Field)

        ' Command #1: Set FG Color (3b: &111)
        ElseIf (#Field > 2) Then
            ' Get FG Color argument
            ExtractField(3)     ' #Field = ExtractBitField(3)
            #Output = ((#Output And MSK_BTAB_FG_COL) + #Field)

        ' Command #0: Continue (4b: &1111)
        Else
            ' Get Skip (Run Length) argument
            ExtractField(4)     ' #Field = ExtractBitField(4)
            Skip = (#Field And $FF)

        End If
    End If

    Return
End

' Input:
'   FieldLen    - The length of the bitfield to read
'   Offset      - The current offset within the buffer
'   #Buffer     - The last packed word read
'
' Output:
'   Field       - The next bitfield of FieldLen requested
'
' Trashed:
'   Temp        - Used for temporary values
'   FieldLen    - Potentialy altered during processing
ExtractBitField: Procedure
    Temp = (16 - Offset)

    ' If there aren't enough bits left in the buffer,
    ' take those first, then force to read a new word
    ' into the buffer for the rest.
    If (FieldLen > Temp) Then
        FieldLen = (FieldLen - Temp)

        ' Get whatever is left from the current buffer
        ' and shift the bits into position ...
        #Field   = ((#Buffer And Pow2Mask(Temp)) * Pow2(FieldLen))
        Offset   = 0
    Else
        #Field   = 0
    End If

    ' Read another word if we've exhausted the buffer.
    If (Offset = 0) Then
        Read #Buffer
    End If

    ' Compose field value and update buffer offset
    #Field  = (#Field + ((#Buffer And Pow2Mask(FieldLen)) / Pow2(FieldLen)))
    Offset  = (Offset + FieldLen)

    Return
End

' Data Tables
' -----------------------------------------------

        ' Table of Powers of 2 (0..15)
Pow2Table:
    DATA $0001, $0002, $0004, $0008, $0010, $0020, $0040, $0080
    DATA $0100, $0200, $0400, $0800, $1000, $2000, $4000, $8000
I will try to test it today, but in the meantime, any feedback or corrections are welcomed. Also, if by chance the entire thing is based on bad assumptions and misguided understanding (which I tend to do occasionally), by all means point that out too.

Download the code below:

unpack.bas 4.43 kB · 4 downloads

Hi DZ,

I've been testing for a while your code for extracting bit files with variable length from a bit stream, but something wasn't working as I expected.

So I have done my own version of the ExtractField in the way I was expecting to be used ?

I've also implemented the simple encoding that we discussed. It is a pure differential encoder without run length encoding.


	INCLUDE "constants.bas"

	MODE SCREEN_FB

	sound 5,0		' Ensure ECS ROMs are mapped out.

	OPTION EXPLICIT ON

	DEF FN ExtractField(Bits) = FieldLen = Bits : Gosub ExtractField

	DIM FieldLen,#WordAdr,#MaxWordAdr,FieldOffset,NextFieldOffset,#Field

	#WordAdr 	= varptr #bitstream(0)
	#MaxWordAdr = varptr #bitstream_end(0)
	FieldOffset = 0

	DIM Idx,#Output,Cmd

	#Output = 7 + 32*8		' only for test, it should be 0
	Idx = 0
	Do
		Gosub ProcessNextCommand
		#BACKTAB(Idx) = #Output
		Idx = (Idx + 1)

	Loop While (Idx < 240)

while (1):wend


' 3 bits for commands + variable lenght filed

'FBT ==Foreground,Backgrounf,Tile
'000  = nothing has changed, repeat last backtab word
'100 +  3 =  6 bits if foreground color changes
'010 +  4 =  7 bits if background color changes
'001 +  7 = 10 bits if tile number changes
'110 +  7 = 10 bits if foreground and background change
'101 + 10 = 13 bits if foreground and tile number change
'011 + 11 = 14 bits if background and tile number change
'111 + 14 = 17 bits if everything changes


Const MSK_BTAB_FG_COL   = &0000000000000111
Const MSK_BTAB_BG_COL   = &0011011000000000
Const MSK_BTAB_PIC      = &0000100111111000

Const MSK_GRAM_FLG      = &0000100000000000

#BackGround:
	DATA $0000     ' BG_BLACK
	DATA $0200     ' BG_BLUE
	DATA $0400     ' BG_RED
	DATA $0600     ' BG_TAN
	DATA $2000     ' BG_DARKGREEN
	DATA $2200     ' BG_GREEN
	DATA $2400     ' BG_YELLOW
	DATA $2600     ' BG_WHITE
	DATA $1000     ' BG_GREY
	DATA $1200     ' BG_CYAN
	DATA $1400     ' BG_ORANGE
	DATA $1600     ' BG_BROWN
	DATA $3000     ' BG_PINK
	DATA $3200     ' BG_LIGHTBLUE
	DATA $3400     ' BG_YELLOWGREEN
	DATA $3600     ' BG_PURPLE


ProcessNextCommand:procedure

	ExtractField(3)

	Cmd = #Field

	if Cmd and 1 then gosub foreground
	if Cmd and 2 then gosub background
	if Cmd and 4 then gosub tile

end

foreground:             procedure
	ExtractField(3)
	#Output = (#Output and (not MSK_BTAB_FG_COL)) + #Field
end
background:             procedure
	ExtractField(4)
	#Output = (#Output and (not MSK_BTAB_BG_COL)) + #BackGround(#Field)
end
tile:                   procedure
	ExtractField(7)
	#Output = (#Output and (not MSK_BTAB_PIC)) + (#Field and &111111)*8 + (MSK_GRAM_FLG and ((#Field and &1000000)>0))
end


ExtractField: procedure

' input:   	FieldLen = number of bits to read (from 0 to 16)
' 			FieldOffset,#WordAdr,#MaxWordAdr = data start and data end pointers
' output: 	#Field value of the FieldLen bits extracted from the stream


' local variables: NextFieldOffset


SIGNED NextFieldOffset

	if (#WordAdr < #MaxWordAdr) then

		NextFieldOffset = FieldLen+FieldOffset-16	' bit offset in the next word

		#Field = peek(#WordAdr) / Pow2Table(FieldOffset)

		if (NextFieldOffset<=0) then 						' all bits within the current word

			#Field = (Pow2Table(FieldLen)-1) and #Field

		else												' you need also bits from the next word

			#Field =  #Field + ((Pow2Table(NextFieldOffset)-1) and peek(#WordAdr+1)) * Pow2Table(16-FieldOffset)

		end if

		FieldOffset = FieldOffset + FieldLen

		if (FieldOffset>15) then

			#WordAdr = #WordAdr + 1

			FieldOffset = FieldOffset and 15

		end if

	end if
end



	   ' Table of Powers of 2 (0..15)
Pow2Table:
	DATA $0001, $0002, $0004, $0008, $0010, $0020, $0040, $0080
	DATA $0100, $0200, $0400, $0800, $1000, $2000, $4000, $8000
	DATA $0000		' used for (2^16) - 1



' Test sequences

#bitstream:
'		 FEDCBA9876543210
 DATA 	&0100001100000000
 DATA 	&0100010100000000
 DATA 	&1000110001110000
 DATA   &0000000000000000
 DATA 	&0100001100000000
 DATA 	&0100010100000000
 DATA 	&1000110001110000
 DATA   &0000000000000000
#bitstream_end:

Aside from the compression ratio, the main concern is the speed of the layer in charge of extracting bits...

I think there is no practical application if the code of ExtractField stays in intybasic because of the speed of multiplications and divisions needed to shift bits inside the word stream.

What do you think ? Can the code be made faster?

I think only an ASM implementation, using shift instructions, could make it usable.

Edited February 12, 2021 by artrag

+DZ-Jay · February 12, 2021

1 hour ago, artrag said:

Hi DZ,

I've been testing for a while your code for extracting bit files with variable length from a bit stream, but something wasn't working as I expected.

So I have done my own version of the ExtractField in the way I was expecting to be used ?

I've also implemented the simple encoding that we discussed. It is not a pure differential encoder without run length encoding.



	INCLUDE "constants.bas"

	MODE SCREEN_FB

	sound 5,0		' Ensure ECS ROMs are mapped out.

	OPTION EXPLICIT ON

	DEF FN ExtractField(Bits) = FieldLen = Bits : Gosub ExtractField

	DIM FieldLen,#WordAdr,#MaxWordAdr,FieldOffset,NextFieldOffset,#Field

	#WordAdr 	= varptr #bitstream(0)
	#MaxWordAdr = varptr #bitstream_end(0)
	FieldOffset = 0

	DIM Idx,#Output,Cmd

	#Output = 7 + 32*8		' only for test, it should be 0
	Idx = 0
	Do
		Gosub ProcessNextCommand
		#BACKTAB(Idx) = #Output
		Idx = (Idx + 1)

	Loop While (Idx < 240)

while (1):wend


' 3 bits for commands + variable lenght filed

'FBT ==Foreground,Backgrounf,Tile
'000  = nothing has changed, repeat last backtab word
'100 +  3 =  6 bits if foreground color changes
'010 +  4 =  7 bits if background color changes
'001 +  7 = 10 bits if tile number changes
'110 +  7 = 10 bits if foreground and background change
'101 + 10 = 13 bits if foreground and tile number change
'011 + 11 = 14 bits if background and tile number change
'111 + 14 = 17 bits if everything changes


Const MSK_BTAB_FG_COL   = &0000000000000111
Const MSK_BTAB_BG_COL   = &0011011000000000
Const MSK_BTAB_PIC      = &0000100111111000

Const MSK_GRAM_FLG      = &0000100000000000

#BackGround:
	DATA $0000     ' BG_BLACK
	DATA $0200     ' BG_BLUE
	DATA $0400     ' BG_RED
	DATA $0600     ' BG_TAN
	DATA $2000     ' BG_DARKGREEN
	DATA $2200     ' BG_GREEN
	DATA $2400     ' BG_YELLOW
	DATA $2600     ' BG_WHITE
	DATA $1000     ' BG_GREY
	DATA $1200     ' BG_CYAN
	DATA $1400     ' BG_ORANGE
	DATA $1600     ' BG_BROWN
	DATA $3000     ' BG_PINK
	DATA $3200     ' BG_LIGHTBLUE
	DATA $3400     ' BG_YELLOWGREEN
	DATA $3600     ' BG_PURPLE


ProcessNextCommand:procedure

	ExtractField(3)

	Cmd = #Field

	if Cmd and 1 then gosub foreground
	if Cmd and 2 then gosub background
	if Cmd and 4 then gosub tile

end

foreground:             procedure
	ExtractField(3)
	#Output = (#Output and (not MSK_BTAB_FG_COL)) + #Field
end
background:             procedure
	ExtractField(4)
	#Output = (#Output and (not MSK_BTAB_BG_COL)) + #BackGround(#Field)
end
tile:                   procedure
	ExtractField(7)
	#Output = (#Output and (not MSK_BTAB_PIC)) + (#Field and &111111)*8 + (MSK_GRAM_FLG and ((#Field and &1000000)>0))
end


ExtractField: procedure

' input:   	FieldLen = number of bits to read (from 0 to 16)
' 			FieldOffset,#WordAdr,#MaxWordAdr = data start and data end pointers
' output: 	#Field value of the FieldLen bits extracted from the stream


' local variables: NextFieldOffset


SIGNED NextFieldOffset

	if (#WordAdr < #MaxWordAdr) then

		NextFieldOffset = FieldLen+FieldOffset-16	' bit offset in the next word

		#Field = peek(#WordAdr) / Pow2Table(FieldOffset)

		if (NextFieldOffset<=0) then 						' all bits within the current word

			#Field = (Pow2Table(FieldLen)-1) and #Field

		else												' you need also bits from the next word

			#Field =  #Field + ((Pow2Table(NextFieldOffset)-1) and peek(#WordAdr+1)) * Pow2Table(16-FieldOffset)

		end if

		FieldOffset = FieldOffset + FieldLen

		if (FieldOffset>15) then

			#WordAdr = #WordAdr + 1

			FieldOffset = FieldOffset and 15

		end if

	end if
end



	   ' Table of Powers of 2 (0..15)
Pow2Table:
	DATA $0001, $0002, $0004, $0008, $0010, $0020, $0040, $0080
	DATA $0100, $0200, $0400, $0800, $1000, $2000, $4000, $8000
	DATA $0000		' used for (2^16) - 1



' Test sequences

#bitstream:
'		 FEDCBA9876543210
 DATA 	&0100001100000000
 DATA 	&0100010100000000
 DATA 	&1000110001110000
 DATA   &0000000000000000
 DATA 	&0100001100000000
 DATA 	&0100010100000000
 DATA 	&1000110001110000
 DATA   &0000000000000000
#bitstream_end:

Aside from the compression ratio, the main concern is the speed of the layer in charge of extracting bits...

I think there is no practical application if the code of ExtractField stays in intybasic because of the speed of multiplications and divisions needed to shift bits inside the word stream.

What do you think ? Can the code be made faster?

I think only an ASM implementation, using shift instructions, could make it usable.

Hi, @artrag,

I'll take a look at it this week-end to see what can be done. Do you by chance know what was not working with the original code?

Also, one thing that I realized after implementation was that, even though all multiplications and divisions were on powers of 2, IntyBASIC couldn't optimize it because the terms were hidden in variables instead of constants.

As you know, in assembly, all those would be a series of bit shifts on registers, which is trivially fast, but IntyBASIC does not give us that option.

That said, I've been studying a little the compiler source code to see if I can exploit my understanding of its code generator to coerce it into producing faster code.

Give me a couple of days to see what I can come up with. I think I have a few more tricks to try.

dZ.

+DZ-Jay · February 12, 2021

Just so that I understand, the problem is with ExtractField itself, you don't need the other part, right?

artrag · February 12, 2021

4 minutes ago, DZ-Jay said:

Just so that I understand, the problem is with ExtractField itself, you don't need the other part, right?

Yes the bottleneck is ExtractField. Its multiplications and divisions make the bit extraction too slow to be practically usable.

Edited February 12, 2021 by artrag

+DZ-Jay · February 12, 2021

19 minutes ago, artrag said:

Yes the bottleneck is ExtractField. Its multiplications and divisions make the bit extraction too slow to be practically usable.

Gotcha. When I wrote it, I naïvely expected it to convert divisions of powers of 2 into shifts. However, it doesn't know they are powers of 2 because they are assigned at runtime, so that can't work.

I think I'll try to use a lookup table and coerce multiplications and divisions on constants.

My biggest problem is that I'm still not very familiar with the language and its idiosyncrasies: I am thinking in low-level assembly and then trying to figure out how to get that generated from IntyBASIC.

I had similar frustrations in trying to integrate the tracker with IntyBASIC.

That said, I'm sure we can figure something out.

dZ.

artrag · February 12, 2021

4 hours ago, DZ-Jay said:

My biggest problem is that I'm still not very familiar with the language and its idiosyncrasies: I am thinking in low-level assembly and then trying to figure out how to get that generated from IntyBASIC.

Provided that Pandora Project is on its own way, maybe the procedure ExtractField could be a very useful tool for everyone if developed in ASM

Maybe using the ASM directive and the naming convention for variables in ASM the integration with intybasic could be easy.

I would try myself but I a total noob with the CP1600

+DZ-Jay · February 12, 2021

35 minutes ago, artrag said:

Provided that Pandora Project is on its own way, maybe the procedure ExtractField could be a very useful tool for everyone if developed in ASM

Maybe using the ASM directive and the naming convention for variables in ASM the integration with intybasic could be easy.

I would try myself but I a total noob with the CP1600

Oh, I can whip up a super-duper fast assembly version of ExtractField pretty easily. :)

-dZ.

+DZ-Jay · February 12, 2021

By the way, expect a faster IntyBASIC version later today. I had forgotten the ability to use "ON xxx GOTO" as a way to generate jump tables. I was going crazy thinking how to optimize a myriad "IF/ELSEIF/ELSE" statements.

I got meetings all morning, but I'm free in the afternoon.

Edited February 12, 2021 by DZ-Jay

+DZ-Jay · February 12, 2021

Hi, @artrag,

I'm working on this. I was actually testing it with sample data (finally!) and noticed a few bugs, which perhaps was what you experienced. Simple things like forgetting to PEEK the value from the Pow2 table (manipulating the address itself). Whoops! ?

My current approach is to replace the macros ShiftLeft() and ShiftRight() with an optimized subroutine that does only shifts. Once I get a successful test, I'll optimize it even further to avoid so many branches.

To give you an idea of what I mean, here are the replacement subroutines:

Spoiler


' ShiftBitsLeft
'   Input:
'     #Temp0    - Value to shift left
'     #Temp1    - Number of bits to shift left
'
'   Output:
'     #Temp0    - Shifted value
ShiftBitsLeft: Procedure
    On #Temp1 Fast GoTo \
        .extract_00, .extract_01, .extract_02, .extract_03, \
        .extract_04, .extract_05, .extract_06, .extract_07, \
        .extract_08, .extract_09, .extract_10, .extract_11, \
        .extract_12, .extract_13, .extract_14, .extract_15

    .extract_00:
        Return

    .extract_01:
        #Temp0 = (#Temp0 / 2)
        Return

    .extract_02:
        #Temp0 = (#Temp0 / 4)
        Return

    .extract_03:
        #Temp0 = (#Temp0 / 8)
        Return

    .extract_04:
        #Temp0 = (#Temp0 / 16)
        Return

    .extract_05:
        #Temp0 = (#Temp0 / 32)
        Return

    .extract_06:
        #Temp0 = (#Temp0 / 64)
        Return

    .extract_07:
        #Temp0 = (#Temp0 / 128)
        Return

    .extract_08:
        #Temp0 = (#Temp0 / 256)
        Return

    .extract_09:
        #Temp0 = (#Temp0 / 512)
        Return

    .extract_10:
        #Temp0 = (#Temp0 / 1024)
        Return

    .extract_11:
        #Temp0 = (#Temp0 / 2048)
        Return

    .extract_12:
        #Temp0 = (#Temp0 / 4096)
        Return

    .extract_13:
        #Temp0 = (#Temp0 / 8192)
        Return

    .extract_14:
        #Temp0 = (#Temp0 / 16384)
        Return

    .extract_15:
        #Temp0 = (#Temp0 / 32768)
        Return
End

' ShiftBitsRight
'   Input:
'     #Temp0    - Value to shift right
'     #Temp1    - Number of bits to shift right
'
'   Output:
'     #Temp0    - Shifted value
ShiftBitsRight: Procedure
    On #Temp1 Fast GoTo \
        .extract_00, .extract_01, .extract_02, .extract_03, \
        .extract_04, .extract_05, .extract_06, .extract_07, \
        .extract_08, .extract_09, .extract_10, .extract_11, \
        .extract_12, .extract_13, .extract_14, .extract_15

    .extract_00:
        Return

    .extract_01:
        #Temp0 = (#Temp0 * 2)
        Return

    .extract_02:
        #Temp0 = (#Temp0 * 4)
        Return

    .extract_03:
        #Temp0 = (#Temp0 * 8)
        Return

    .extract_04:
        #Temp0 = (#Temp0 * 16)
        Return

    .extract_05:
        #Temp0 = (#Temp0 * 32)
        Return

    .extract_06:
        #Temp0 = (#Temp0 * 64)
        Return

    .extract_07:
        #Temp0 = (#Temp0 * 128)
        Return

    .extract_08:
        #Temp0 = (#Temp0 * 256)
        Return

    .extract_09:
        #Temp0 = (#Temp0 * 512)
        Return

    .extract_10:
        #Temp0 = (#Temp0 * 1024)
        Return

    .extract_11:
        #Temp0 = (#Temp0 * 2048)
        Return

    .extract_12:
        #Temp0 = (#Temp0 * 4096)
        Return

    .extract_13:
        #Temp0 = (#Temp0 * 8192)
        Return

    .extract_14:
        #Temp0 = (#Temp0 * 16384)
        Return

    .extract_15:
        #Temp0 = (#Temp0 * 32768)
        Return
End

I haven't studied your version yet, but I will. I'll report back when I have something.

-dZ.

Edited February 12, 2021 by DZ-Jay

+DZ-Jay · February 14, 2021

Hello, @artrag,

I have fixed the bugs in my ExtractBitField() routine. Boy, was it full of subtle errors, like off-by-one and forgetting to de-reference addresses. ?

Anyway, I have actually tested it this time, in the debugger, to make sure it works. I've tested extracting bits at or across word boundaries, and it seems to work.

I tried to optimize the IntyBASIC code to reduce expression evaluations and variable access, and I'm sure more can be done. Right now, some of the statements require multiple read/write operations on the same variable memory when evaluating a single expression. When I see that on the assembled code, it hurts my eyes! :grin:

The big optimization right now, which perhaps is sufficient to the code you wrote, is the implementation of the ShiftLeft() and ShiftRight() macros as a jump table that respectively multiplies or divides a value by a constant. With that, IntyBASIC then assembles all division and multiplication operations as bitwise operations on a register (shift, and, etc.), which is ultimately what we want.

(On that note, I realized that IntyBASIC only optimizes multiplication and division of powers of two up to 256, which explains why I see a lot of programs with things like "m = n / 256 / 4", and such. That always seemed weird to me, but now I know why.)

The problem is in the abstraction for reusability: because BASIC doesn't support passing arguments to subroutines, we are left with using global temporary variables: so we must put our parameters in global variables, and then read them back into our original variables. Once again, I'm sure there is an opportunity to optimize that as well.

Below is the updated ExtractBitField() routine with its dependencies. I will work on testing and debugging my original decoding algorithm to provide a reference implementation for others, but I wanted to have this part ready for you, since it is all you need right now.

I hope it is useful.

Spoiler


' Constants
' -----------------------------------------------
Const MSK_CMD           = &0000000000000111
Const MSK_CMD_POST_FLG  = &0000000000000100
Const MSK_CMDARG_0      = &0000000000001111
Const MSK_CMDARG_1      = &0000000000000111
Const MSK_CMDARG_2      = &0000000000011011
Const MSK_CMDARG_3      = &0000000000111111
Const MSK_CMDARG_GRAM   = &0000000000100000

Const MSK_BTAB_FG_COL   = &0000000000000111
Const MSK_BTAB_BG_COL   = &0011011000000000
Const MSK_BTAB_PIC      = &0000100111111000

Const MSK_GRAM_FLG      = &0000100000000000
Const BUFFER_OFFS_EMTPY = 16
Const BUFFER_OFFS_FULL  = 0
Const NULL              = 0

' Macros
' -----------------------------------------------
DEF FN Pow2(Exp)            = Peek(VarPtr Pow2Table(Exp))
DEF FN Pow2Mask(Exp)        = (Pow2(Exp) - 1)
DEF FN ExtractField(Bits)   = FieldLen = Bits : Gosub ExtractBitField
DEF FN ShiftLeft(Val, Bits) = #Temp0 = Val : #Temp1 = Bits : Gosub ShiftBitsLeft
DEF FN ShiftRight(Val, Bits)= #Temp0 = Val : #Temp1 = Bits : Gosub ShiftBitsRight

' Variables
' -----------------------------------------------
Dim Offset
Dim FieldLen
Dim #Temp0
Dim #Temp1
Dim #Field
Dim #Buffer

' ExtractBitField
'   Input:
'     FieldLen    - The length of the bitfield to read
'     Offset      - The current offset within the buffer
'     #Buffer     - The last packed word read
'
'   Output:
'     Offset      - New buffer offset position
'     #Field      - The next bitfield of FieldLen requested
'
'   Trashed:
'     FieldLen    - Potentialy altered during processing
ExtractBitField: Procedure
    ' If there aren't enough bits left in the buffer,
    ' take those first, then force to read a new word
    ' into the buffer for the rest.
    If (FieldLen > Offset) Then
        FieldLen = (FieldLen - Offset)

        ' Get whatever is left from the current buffer
        ' and shift the bits into position, to open
        ' space for the missing ones.
        '
        ' We do not need to shift the mask because we
        ' assume that the field is in the LSBs.
        ShiftLeft((#Buffer And Pow2Mask(Offset)), FieldLen)
        #Field   = #Temp0
        Offset   = BUFFER_OFFS_EMTPY
    Else
        #Field   = NULL
    End If

    ' Read another word if we've exhausted the buffer.
    If (Offset = BUFFER_OFFS_EMTPY) Then
        Read #Buffer
    End If

    ' Compose field value and update buffer offset
    Offset = (Offset - FieldLen)
    ShiftRight(#Buffer, Offset)

    ' By masking the field after shifting, we avoid
    ' having to align the mask.  We then mask always
    ' starting at the LSB.
    #Field  = (#Field + (#Temp0 And Pow2Mask(FieldLen)))
    Return
End

' ShiftBitsLeft
'   Input:
'     #Temp0    - Value to shift left
'     #Temp1    - Number of bits to shift left
'
'   Output:
'     #Temp0    - Shifted value
ShiftBitsLeft: Procedure
    On #Temp1 Fast GoTo \
        .extract_00, .extract_01, .extract_02, .extract_03, \
        .extract_04, .extract_05, .extract_06, .extract_07, \
        .extract_08, .extract_09, .extract_10, .extract_11, \
        .extract_12, .extract_13, .extract_14, .extract_15

    .extract_00:
        ' #Temp0 = (#Temp0 * 1)           ' × 2^0 = 1  <-- Yeah, we skip this one! ;)
        Return

    .extract_01:
        #Temp0 = (#Temp0 * 2)           ' × 2^1 = 2
        Return

    .extract_02:
        #Temp0 = (#Temp0 * 4)           ' × 2^2 = 4
        Return

    .extract_03:
        #Temp0 = (#Temp0 * 8)           ' × 2^3 = 8
        Return

    .extract_04:
        #Temp0 = (#Temp0 * 16)          ' × 2^4 = 16
        Return

    .extract_05:
        #Temp0 = (#Temp0 * 32)          ' × 2^5 = 32
        Return

    .extract_06:
        #Temp0 = (#Temp0 * 64)          ' × 2^6 = 64
        Return

    .extract_07:
        #Temp0 = (#Temp0 * 128)         ' × 2^7 = 128
        Return

    .extract_08:
        #Temp0 = (#Temp0 * 256)         ' × 2^8 = 256
        Return

    .extract_09:
        #Temp0 = (#Temp0 * 256 * 2)     ' × 2^9 = 512
        Return

    .extract_10:
        #Temp0 = (#Temp0 * 256 * 4)     ' × 2^10 = 1,024
        Return

    .extract_11:
        #Temp0 = (#Temp0 * 256 * 8)     ' × 2^11 = 2,048
        Return

    .extract_12:
        #Temp0 = (#Temp0 * 256 * 16)    ' × 2^12 = 4,096
        Return

    .extract_13:
        #Temp0 = (#Temp0 * 256 * 32)    ' × 2^13 = 8,192
        Return

    .extract_14:
        #Temp0 = (#Temp0 * 256 * 64)    ' × 2^14 = 16,384
        Return

    .extract_15:
        #Temp0 = (#Temp0 * 256 * 128)   ' × 2^15 = 32,768
        Return
End

' ShiftBitsRight
'   Input:
'     #Temp0    - Value to shift right
'     #Temp1    - Number of bits to shift right
'
'   Output:
'     #Temp0    - Shifted value
ShiftBitsRight: Procedure
    On #Temp1 Fast GoTo \
        .extract_00, .extract_01, .extract_02, .extract_03, \
        .extract_04, .extract_05, .extract_06, .extract_07, \
        .extract_08, .extract_09, .extract_10, .extract_11, \
        .extract_12, .extract_13, .extract_14, .extract_15

    .extract_00:
        ' #Temp0 = (#Temp0 / 1)           ' ÷ 2^0 = 1  <-- Yeah, we skip this one! ;)
        Return

    .extract_01:
        #Temp0 = (#Temp0 / 2)           ' ÷ 2^1 = 2
        Return

    .extract_02:
        #Temp0 = (#Temp0 / 4)           ' ÷ 2^2 = 4
        Return

    .extract_03:
        #Temp0 = (#Temp0 / 8)           ' ÷ 2^3 = 8
        Return

    .extract_04:
        #Temp0 = (#Temp0 / 16)          ' ÷ 2^4 = 16
        Return

    .extract_05:
        #Temp0 = (#Temp0 / 32)          ' ÷ 2^5 = 32
        Return

    .extract_06:
        #Temp0 = (#Temp0 / 64)          ' ÷ 2^6 = 64
        Return

    .extract_07:
        #Temp0 = (#Temp0 / 128)         ' ÷ 2^7 = 128
        Return

    .extract_08:
        #Temp0 = (#Temp0 / 256)         ' ÷ 2^8 = 256
        Return

    .extract_09:
        #Temp0 = (#Temp0 / 256 / 2)     ' ÷ 2^9 = 512
        Return

    .extract_10:
        #Temp0 = (#Temp0 / 256 / 4)     ' ÷ 2^10 = 1,024
        Return

    .extract_11:
        #Temp0 = (#Temp0 / 256 / 8)     ' ÷ 2^11 = 2,048
        Return

    .extract_12:
        #Temp0 = (#Temp0 / 256 / 16)    ' ÷ 2^12 = 4,096
        Return

    .extract_13:
        #Temp0 = (#Temp0 / 256 / 32)    ' ÷ 2^13 = 8,192
        Return

    .extract_14:
        #Temp0 = (#Temp0 / 256 / 64)    ' ÷ 2^14 = 16,384
        Return

    .extract_15:
        #Temp0 = (#Temp0 / 256 / 128)   ' ÷ 2^15 = 32,768
        Return
End

' Data Tables
' -----------------------------------------------

        ' Table of Powers of 2 (0..15)
Pow2Table:
    DATA    $0001, $0002, $0004, $0008, $0010, $0020, $0040, $0080
    DATA    $0100, $0200, $0400, $0800, $1000, $2000, $4000, $8000

-dZ.

extractbits.bas

Edited February 14, 2021 by DZ-Jay

artrag · February 14, 2021

Just a note. This line

Peek(VarPtr Pow2Table(Exp))

is equivalent to

Pow2Table(Exp)

+DZ-Jay · February 14, 2021

1 hour ago, artrag said:

Just a note. This line

Peek(VarPtr Pow2Table(Exp))

is equivalent to

Pow2Table(Exp)

Ah! Thanks, you are absolutely right. For some reason, I thought you needed VarPtr to reference an array using a label to data instead of a variable in RAM. I see that it is not so.

At least the compiler is smart enough to treat it the same and compiles identically. :)

I'll update the reference implementation.

Thanks!

-dZ.

+DZ-Jay · February 15, 2021

I've updated post #7 above to correct some errors in the description of the algorithm, and to include the final tested version of the reference implementation. I've also attached the module to this post, for convenience.

I will create a new thread for it, just to have it ready for anybody who could use it.

-dZ.

Attached files:

pkscn.bas - Sample IntyBASIC project for testing
unpack.bas - Reference Implementation of "BACKTAB Unpack" algorithm

packing data with variable length

Recommended Posts

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Join the conversation

Recently Browsing 0 members