Algorithm Advice: Read Saturn Save without Malloc()

[slinga]

Still working on libslinga (GitHub - slinga-homebrew/libslinga: Sega Saturn save game library).

I'm trying to think of an algorithm to read a Sega Saturn save file without the need for malloc(), large stack space, or a large global buffer. For Save Game Copier I used jo_malloc() to allocate a buffer to store the block ids. With libslinga I am not assuming I have access to malloc(). The official BUP library preallocated a large section of memory (4k bytes?) to use for this table.

Additional information:
- Save-Game-Copier/backends/sat.h at master · slinga-homebrew/Save-Game-Copier
- Save-Game-Copier/backends/sat.c at master · slinga-homebrew/Save-Game-Copier - getSatBlocks() reads the block IDs into a dynamically allocated buffer. getSATSave() reads the save by walking the list of block IDs.

//
// SAT structures
//
//
// Saturn saves are stored in 64-byte blocks
// - the first 4 bytes of each block is a tag
// -- 0x80000000 = start of new save
// -- 0x00000000 = continuation block?
// - the next 30 bytes are metadata for the save (save name, language, comment, date, and size)
// -- the size is the size of the save data not counting the metadata
// - next is a variable array of 2-byte block ids. This array ends when 00 00 is encountered
// -- the block id for the 1st block (the one containing the metadata) is not present. In this case only 00 00 will be present
// -- the variable length array can be 0-512 elements (assuming max save is on the order of ~32k)
// -- to complicate matters, the block ids themselves can extend into multiple blocks. This makes computing the block count tricky
// - following the block ids is the save data itself

*// -- to complicate matters, the block ids themselves can extend into multiple blocks. This makes computing the block count tricky* this is what makes parsing the SAT table tricky. In SGC I reduced the complexity by just reading the entire table into a dynamically allocated array and working with that.

Assuming a maximum save of ~32k for internal memory
-- by my calculations 29,548 byte save will take 510 blocks. 2 blocks are overhead. 512 blocks x 64 bytes per block = 32k.
-- 510 blocks * 2 bytes each = 1020 bytes for the SAT table.

Assuming a maximum save of 256k:
- I need 4,521 blocks
- 4,521 * 2 = 9,042 bytes for the sat table

I'm trying to think of an algorithm to read the SAT blocks without having to allocate the SAT table. I think there might be something to reading the save backwards, but I haven't come up with an algorithm yet. I will also need the reverse to be able to write a save as well.

I plan to think hard this weekend.

 

[Knight0fDragon]

Calculate total block count:

let dataSize = file.size
let metaSize = 32
var bytesNeeded = dataSize + metaSize
var blocksNeeded = roundUp(bytesNeeded / 60)
var currentBlocksNeeded = blocksNeeded - 1 //subtract 1 because we already have a block
do
    let remainderSpace = bytesNeeded * 60 - totalSize //remainderSpace is space left within a block.

    let blockTableSize = currentBlocksNeeded * 2
    bytesNeeded =   blockTableSize - remainderSpace
    currentBlocksNeeded = roundUp(bytesNeeded / 60)
    blocksNeeded += currentBlocksNeeded
while(currentBlocksNeeded>0)
print(blockedNeeded)

Calculate table length:

var tableLength = 1 //Account for null ending
let dataSize = file.size
let metaSize = 32
var bytesNeeded = dataSize + metaSize
var blocksNeeded = roundUp(bytesNeeded / 60)
var currentBlocksNeeded = blocksNeeded - 1 //subtract 1 because we already have a block
do
    let remainderSpace = bytesNeeded * 60 - totalSize //remainderSpace is space left within a block.
    let blockTableSize = currentBlocksNeeded * 2
    tableLength += currentBlocksNeeded
    bytesNeeded =   blockTableSize - remainderSpace
    currentBlocksNeeded = roundUp(bytesNeeded / 60)
    blocksNeeded += currentBlocksNeeded
while(currentBlocksNeeded>0)
print(tableLength)

*Note, you could walk through the table until you find zero, but the algorithm becomes complex since you need to account for potentially blocks consisting of nothing but the block id table.


Calculate padding:

var tableLength = 1 //Account for null ending
let dataSize = file.size
let metaSize = 32
var bytesNeeded = dataSize + metaSize
var blocksNeeded = roundUp(bytesNeeded / 60)
var currentBlocksNeeded = blocksNeeded - 1 //subtract 1 because we already have a block
var padding = 0
do
    let remainderSpace = bytesNeeded * 60 - totalSize //remainderSpace is space left within a block.
    let blockTableSize = currentBlocksNeeded * 2
    tableLength += currentBlocksNeeded
    bytesNeeded =   blockTableSize - remainderSpace
    currentBlocksNeeded = roundUp(bytesNeeded / 60)
    blocksNeeded += currentBlocksNeeded
    padding = remainderSpace
while(currentBlocksNeeded>0)
print(padding)

*Need to think this through, since you have a scenario where your block is only block table IDs.
To avoid using malloc. You want to do the following:

let mainBlock = readBlock(startingID)
let blockIDTablePtr = mainBlock.tablePtr
process(mainBlock.dataPtr,mainBlock.dataLength)
var remainingFileSize = file.size - mainBlock.dataLength
while(*blockIDTablePtr != 0)
    let block =  readBlock(*blockIDTablePtr)
    let dataLength = min(remainingFileSize,block.dataLength)
    process(block.dataPtr,dataLength)
    remainingFileSize -= dataLength
    blockIDTablePtr += 1

Where readBlock returns your bup struct. On your main read, you should see the meta filled in, and on data reads, only the data section should have info in it.

readBlock would just need a static allocation to accommodate the block being read.

process is basically whatever you need to do with the segmented chunk of data.

 

[slinga]

I ended up going with a large (1024 bitmap). I checked in my code to GitHub - slinga-homebrew/libslinga: Sega Saturn save game library.

The basic idea is each bit in the bitmap represents a block on the partition.

g_SAT_bitmap[] is a large bitmap used to store free\busy blocks
each bitmap represents a single block

Internal memory
- 0x8000 partition size
- 0x40 block size
- bytes needed = 0x8000 / 0x40 / 8 (bits per byte) = 0x40 (64) bytes

32 Mb Cartridge
- 0x400000 partition size
- 0x400 block size
- bytes needed - 0x400000 / 0x400 / 8 (bits per byte_ = 0x200 (512) bytes

Action Replay
- 0x80000 partition size
- 0x40 block size
- bytes needed = 0x80000 / 0x40 / 8 (bits per byte) = 0x400 (1024) bytes

This means we need a 1024 byte buffer to support the Action Replay. I can play around with #defs to reduce the size to 512 (or 64) depending on which devices are compiled in.