Extending the MMB format beyond 511 disks

[Coeus]

The big attraction of Nx511 disk chunk scheme is you can simply cat together seperate archives, then just tweak the first header with dd:

Could you further simplify this by working out how many chunks of 512 images are in the file from the FAT32 catalogue entry for the MMB file? That does assume, of course, that no software writes short MMB files. But that way one would be able to cat and split these files using just the cat and split Unix commands. To be fair you can use split anyway if you patch the header of the first resulting file.

[Coeus]

Overall, the performance difference is negligble. Both schemes have a very small (but just about mearurable) performance impact.

...

Each is called once per file operation in the benchmark (I checked this).

Is there enough workspace left to mitigate this by doing the calculation at *DIN time and holding the calculated start of disc offset for each mountend image rather than holding the disc number?

Naively, this would need 4x4=16 bytes as each offset would need to be 32 bits but maybe the least signficant byte need not be stored as I think it would always be the same, possibly zero.

[hoglet]

Is there enough workspace left to mitigate this by doing the calculation at *DIN time and holding the calculated start of disc offset for each mountend image rather than holding the disc number?

Not really - there are only a few spare bytes in the part of the absolute workspace that gets saved to private workspace (&10C0-&10CF)

It would also need to be placed in the CRC protected part, which is even smaller, otherwise if it gets corrupted then random sectors could get written.

Dave

[Coeus]

But for one reason or another I find myself still using MMFSv1, mostly because I have a much better memory for disk numbers than for 8-character filenames. But partly because I have found MMFSv2 a bit slow with large numbers of disks.

So referring to my post about pre-calculating the disc offset, is MMFSv2 also re-searching the FAT directory for the filename on each file access. You would certainly expect that to slow it down and more so for entries that are later in the catalogue. If so it would be good to cache it, if possible.

[Coeus]

Not really - there are only a few spare bytes in the part of the absolute workspace that gets saved to private workspace (&10C0-&10CF)

It would also need to be placed in the CRC protected part, which is even smaller, otherwise if it gets corrupted then random sectors could get written.

That's a pity. It would only need 4 more bytes, i.e. storing the offset instead of the disc number, not as well as. Another possibility would be to re-calculate it whenever MMFS gets the absolute workspace back.

[TobyLobster]

I think this may be one or two bytes longer, but it should be much quicker in execution. Because 511 is one less than a power of two, there are optimisations to be had. This has no loops. The result of the division is in A on exit, with the remainder in dmret/dmret+1.

Code: Select all

.calculate_div_mod_511_zp_x
{
    LDA 1, X
    LSR A
    BCC done
    EOR #255
    CMP 0, X
    BEQ addone
    BCS invertdone
.addone
    SEC
    SBC #1
.invertdone
    EOR #255
.done
    PHA
    CLC
    ADC 0, X
    STA dmret%
    LDA 1, X
    ADC #0
    AND #1
    STA dmret%+1
    PLA
    RTS
}

For testing purposes I used this code to check every possible input:

Code: Select all

REM 16 bit divide by 511
REM
MODE 7
NEW
AUTO
DIM mem% 100
FOR I%=0 TO 2 STEP 2
P%=mem%
[OPT I%
    LDA 1, X
    LSR A
    BCC done
    EOR #255
    CMP 0, X
    BEQ addone
    BCS invertdone
.addone
    SEC
    SBC #1
.invertdone
    EOR #255
.done
    PHA
    CLC
    ADC 0, X
    STA dmret
    LDA 1, X
    ADC #0
    AND #1
    STA dmret+1
    PLA
    RTS
.dmret
    EQUW 0
]
NEXT I%
:
FOR A%=0 TO 65535
  X%=&70
  ?X% = A%
  X%?1 = A% / 256
  D%=USR(mem%) AND 255
  R%=?dmret + 256 * dmret?1
  IF (D% <> (A% DIV 511)) THEN PRINT "Error! ";A%:END
  IF (R% <> (A% MOD 511)) THEN PRINT "Error! ";A%:END
  IF ((A% AND 255) = 0) THEN PRINT ;~A%;" ";
NEXT
END

[Coeus]

I'm patricularly proud of spotting a BPUT/BGET optimization that saves 52 bytes:
https://github.com/hoglet67/MMFS/commit/78da4d18

It did check it sthey still work using Tom Seddon's file system tester.

I am not sure if it is necessarily any better but the BYTEIO version of the filing system tester I wrote for VDFS is OK with the change. What that does is take 109 lines from Shakespeare's Jullius Caesar, writes them sequentially to a test file then reads them back both sequentially and at random and compares with the original. It then repeats the test writing the test file randomly:

The original v1.49 without either big MMB or BGET/BPUT optimisation

Version 1.4Y with big MMFS and BGET/BPUT optimisation.

The code is at https://github.com/SteveFosdick/FsTest

[Coeus]

I think this may be one or two bytes longer, but it should be much quicker in execution. Because 511 is one less than a power of two, there are optimisations to be had. This has no loops. The result of the division is in A on exit, with the remainder in dmret/dmret+1.

If I try subsituting this code into the relevant place in MMFS, it does not work and various errors are reported.

Looking more closely, the code is entered with the dividend at 00,X (16 bit) with the divisor fixed as 511. The quotient is returned in X and the remainder in dmret (16bit).

Your replacement seems to still return the remainder in dmret but leaves X the same as on entry, i.e. it does not return the quotient.

[Coeus]

Do we have a test MMB file?

[TobyLobster]

Your replacement seems to still return the remainder in dmret but leaves X the same as on entry, i.e. it does not return the quotient.

In my version the quotient is returned in A. So add a TAX at the end.

[dp11]

Slightly faster, by moving some of the carry setting and clearing.https://bbcmic.ro/#%7B%22v%22%3A1%2C%22 ... nEND%22%7D

[hoglet]

I think this may be one or two bytes longer, but it should be much quicker in execution. Because 511 is one less than a power of two, there are optimisations to be had. This has no loops. The result of the division is in A on exit, with the remainder in dmret/dmret+1.

This is very interesting, thanks.

Do you have a reference to the algorithm it uses, or the maths that undepins it?

I need to do some cycle counting, but I guess for disks 0..510 it may be a tad slower, but then as the number of chunks increases it will be increasing faster.

[I am not sure if it is necessarily any better but the BYTEIO version of the filing system tester I wrote for VDFS is OK with the change. What that does is take 109 lines from Shakespeare's Jullius Caesar, writes them sequentially to a test file then reads them back both sequentially and at random and compares with the original. It then repeats the test writing the test file randomly:

This sounds like a good test to have run, and I'm reasurred that it passes.

Do we have a test MMB file?

I'll post a link to one of my test MMB files later today,

You can also make your own by:
- concatenating together N existing 511 disk MMB files (check they are all 104,660,992 byes long)
- set byte 8 to 0xA0 + N - 1

For example,

Code: Select all

cat 1.MMB 2.MMB > BEEB.MMB
$ printf '\xA1' | dd of=BEEB.MMB bs=1 seek=8 count=1 conv=notrunc

Tricky's MMB file is here:
viewtopic.php?f=2&t=16070

One of mine is here:
https://github.com/hoglet67/Ice40Beeb/r ... EB.MMB.zip

Dave

[TobyLobster]

Do you have a reference to the algorithm it uses, or the maths that undepins it?

I'm sure there must be references out there somewhere, but I don't know them. I realised that x/511 is going to be close to x/512, so I differenced the two and saw that the difference was either zero or one, then worked out that it was possible to calculate when it was necessary to add one to the result. Similarly the modulus is close to (x & 511) which can be fixed by adding result of the division first. I'd guess similar results are possible for other 2^n-1 divisions, and I'd imagine for 2^n+1 too.

EDIT: For small integer divisions https://web.archive.org/web/20170421094 ... 6562c77288

[TobyLobster]

Slightly faster, by moving some of the carry setting and clearing.

Nice!

[BigEd]

Slightly faster, by moving some of the carry setting and clearing.

Nice!

You can get access to 'rocket mode' in owlet by putting in ?experimental=true before the hashmark, and get JIT performance:
https://bbcmic.ro/?experimental=true#%7 ... nEND%22%7D

[dp11]

Slightly faster, by moving some of the carry setting and clearing.

Nice!

You can get access to 'rocket mode' in owlet by putting in ?experimental=true before the hashmark, and get JIT performance:
https://bbcmic.ro/?experimental=true#%7 ... nEND%22%7D

I was trying to remember how to access rocket mode this morning. how did you know ?

[hoglet]

Do you have a reference to the algorithm it uses, or the maths that undepins it?

I'm sure there must be references out there somewhere, but I don't know them. I realised that x/511 is going to be close to x/512, so I differenced the two and saw that the difference was either zero or one, then worked out that it was possible to calculate when it was necessary to add one to the result. Similarly the modulus is close to (x & 511) which can be fixed by adding result of the division first. I'd guess similar results are possible for other 2^n-1 divisions, and I'd imagine for 2^n+1 too.

Thanks for the explanation, that's very clever.

I've think I've come up with an improved implementation that saves 8 bytes:

Code: Select all

    LDA 1, X
    LSR A
    PHA
    BCC done
    ADC 0, X	; C = 1 if correction of quotient is needed
    PLA
    ADC #0	; correct the quotient by +1
    PHA
.done
    ADC 0, X
    STA dmret
    LDA 1, X
    ADC #0
    AND #1
    STA dmret+1
    PLA
    RTS

Original iterative version: 29 bytes

Toby's direct version: 34 bytes (+1 for the TAX)

Dave's tweak to Toby's direct version: 26 bytes (+1 for the TAX)

Here's that version in Owlet: link

I'm definitely going to switch to this approach.

Dave

[TobyLobster]

Dave's: 26 bytes (+1 for the TAX)

Nice!

[hoglet]

Nice!

And actually, returning the quotient in A works out fine; it allows me to remove two TXA instrructions.

Overall we save 4 bytes (compared to the original iterative version) and it's much faster.

Dave

[sweh]

His it been decided that the 511-concatenated version is the direction forward? Or are people still making up their minds?

[hoglet]

Here's the final version of the DIV/MOD 511 subroutine with comments:
https://github.com/hoglet67/MMFS/blob/5 ... .asm#L6498

Do we have a test MMB file?

Here's my current test file with 16 chunks:
https://www.dropbox.com/s/t4iq4qca0zzlg ... MB.gz?dl=1

Chunk 0 is my BEEB.MMB file

Chunk 1 is Tricky's BEEB.MMB file

Chunk 2..8 are SSD files from bbcmicro.co.uk

Chunks 9..15 are free.

Dave

[hoglet]

His it been decided that the 511-concatenated version is the direction forward? Or are people still making up their minds?

I'd definitely like to go this way.

I don't have any concerns about performance or space usage now.

Unless there are any strong objections, I think we should move ahead on that basis.

There's one more feature I would like to try to add, then I'll release a MMFS 1.50.

Dave

[BigEd]

Sounds great!

[robcfg]

Ok, I’ll add support for it during the weekend.

[tricky]

I'll add an option to always output 511 image MMB files to my menu generator as it currently rounds up to three next power of 2 if it doesn't need the full 511. If it needs more than 511, the first will be 511 anyway.

[Coeus]

Here's my current test file with 16 chunks:
https://www.dropbox.com/s/t4iq4qca0zzlg ... MB.gz?dl=1
...

Dave, the current code in MMFS has:

Code: Select all

	\\ Read the 8th byte of the disk table which now  indicates it's size:
	\\ 	8th byte	DISK_TABLE_SIZE
	\\	0x00	     	0x10	(0x01FF disks) (original value of 511)
	\\	0x01		0x20	(0x03FE disks)
	\\	0x02		0x30	(0x05FD disks)
	\\      ...
	\\      0x0E		0xF0	(0x1DF1 disks)
	\\      0x0F		0x00	(0x1FF0 disks)
	\\ Any other value default to 511

But that test file has &AF in as the 8th byte. Was it your intention to keep the upper nibble as &A to indicate an extended file, as proposed much earlier, or is the comment in the MMFS code now correct that the top nibble is either zero or should just be ignored?

[hoglet]

But that test file has &AF in as the 8th byte. Was it your intention to keep the upper nibble as &A to indicate an extended file, as proposed much earlier, or is the comment in the MMFS code now correct that the top nibble is either zero or should just be ignored?

I need to fix the comment.

I would like to keep the upper nibble as &A, just in case there are MMB files around where that byte is non-zero (0xFF for example).

The MMFS behaviour is that &A1..&AF indicate extended files (2..16 chunks)

Anything else should be treated as just a single chunk (i.e. an original 511 disk archive)

Dave

[hoglet]

Comment is fixed now (on the large_mmb_support2 branch)

[sweh]

I would like to keep the upper nibble as &A, just in case there are MMB files around where that byte is non-zero (0xFF for example).

I'm using it as a sanity check; if it's not zero and not A# then I report it as potentially corrupt. I could add FF as an allowed value meaning zero I guess.

Some new commands coming in my perl tools

Code: Select all

$ beeb dblank_mmb -h
Syntax: dblank_mmb [-f MMB_file] [extra_catalogs]
   extra_catalogues must be a number between 1 and 15 inclusive

$ beeb dblank_mmb 5
Blank BEEB.MMB created (with 5 additional catalogues)

$ beeb dmmb_info
MMB Filename: BEEB.MMB
  Number of extents: 6
    Number of disks: 3066
       #Unformatted: 3066

$ beeb dextend_mmb
BEEB.MMB extended

$ beeb dmmb_info  
MMB Filename: BEEB.MMB
  Number of extents: 7
    Number of disks: 3577
       #Unformatted: 3577

$ beeb dmmb_info -f Hoglet_MMB 
MMB Filename: Hoglet_MMB
  Number of extents: 16
    Number of disks: 8176
       #Unformatted: 3682

[sweh]

Base commands also seem to work... let's copy one file out of Hoglet's MMB, store it in an extended catalogue on the new blank MMB, check it's there, re-extract it and verify the contents are unchanged

Code: Select all

$ beeb dget_ssd -f Hoglet_MMB 269 pi.ssd
Getting disk 269: Pi 1MHz     
pi.ssd created

$ beeb dput_ssd 1234 pi.ssd 
Disk pi.ssd (Pi 1MHz) written to 1234

$ beeb dcat
1234: Pi 1MHz   

$ beeb dget_ssd 1234 new.ssd
Getting disk 1234: Pi 1MHz     
new.ssd created

$ diff pi.ssd new.ssd 
$ 

Yay!