Extending the MMB format beyond 511 disks

discuss both original and modern hardware for the bbc micro/electron
Coeus
Posts: 2360
Joined: Mon Jul 25, 2016 12:05 pm
Contact:

Re: Extending the MMB format beyond 511 disks

Post by Coeus »

hoglet wrote:
Sat Sep 25, 2021 5:04 pm
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
Posts: 2360
Joined: Mon Jul 25, 2016 12:05 pm
Contact:

Re: Extending the MMB format beyond 511 disks

Post by Coeus »

hoglet wrote:
Sat Sep 25, 2021 3:29 pm
Overall, the performance difference is negligble. Both schemes have a very small (but just about mearurable) performance impact.
...
hoglet wrote:
Sat Sep 25, 2021 3:29 pm
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.
User avatar
hoglet
Posts: 10598
Joined: Sat Oct 13, 2012 7:21 pm
Location: Bristol
Contact:

Re: Extending the MMB format beyond 511 disks

Post by hoglet »

Coeus wrote:
Mon Sep 27, 2021 4:36 pm
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
Posts: 2360
Joined: Mon Jul 25, 2016 12:05 pm
Contact:

Re: Extending the MMB format beyond 511 disks

Post by Coeus »

hoglet wrote:
Thu Sep 23, 2021 6:12 pm
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
Posts: 2360
Joined: Mon Jul 25, 2016 12:05 pm
Contact:

Re: Extending the MMB format beyond 511 disks

Post by Coeus »

hoglet wrote:
Mon Sep 27, 2021 4:51 pm
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.
User avatar
TobyLobster
Posts: 170
Joined: Sat Aug 31, 2019 7:58 am
Contact:

Re: Extending the MMB format beyond 511 disks

Post by 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
Posts: 2360
Joined: Mon Jul 25, 2016 12:05 pm
Contact:

Re: Extending the MMB format beyond 511 disks

Post by Coeus »

hoglet wrote:
Sun Sep 26, 2021 5:10 pm
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
The original v1.49 without either big MMB or BGET/BPUT optimisation
Version 1.4Y with big MMFS and BGET/BPUT optimisation.
Version 1.4Y with big MMFS and BGET/BPUT optimisation.
The code is at https://github.com/SteveFosdick/FsTest
Coeus
Posts: 2360
Joined: Mon Jul 25, 2016 12:05 pm
Contact:

Re: Extending the MMB format beyond 511 disks

Post by Coeus »

TobyLobster wrote:
Mon Sep 27, 2021 10:38 pm
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
Posts: 2360
Joined: Mon Jul 25, 2016 12:05 pm
Contact:

Re: Extending the MMB format beyond 511 disks

Post by Coeus »

Do we have a test MMB file?
User avatar
TobyLobster
Posts: 170
Joined: Sat Aug 31, 2019 7:58 am
Contact:

Re: Extending the MMB format beyond 511 disks

Post by TobyLobster »

Coeus wrote:
Mon Sep 27, 2021 11:42 pm
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
Posts: 1332
Joined: Sun Aug 12, 2012 9:47 pm
Contact:

Re: Extending the MMB format beyond 511 disks

Post by dp11 »

Slightly faster, by moving some of the carry setting and clearing.https://bbcmic.ro/#%7B%22v%22%3A1%2C%22 ... nEND%22%7D
User avatar
hoglet
Posts: 10598
Joined: Sat Oct 13, 2012 7:21 pm
Location: Bristol
Contact:

Re: Extending the MMB format beyond 511 disks

Post by hoglet »

TobyLobster wrote:
Mon Sep 27, 2021 10:38 pm
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.
Coeus wrote:
Mon Sep 27, 2021 11:06 pm
[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.
Coeus wrote:
Tue Sep 28, 2021 2:50 am
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
User avatar
TobyLobster
Posts: 170
Joined: Sat Aug 31, 2019 7:58 am
Contact:

Re: Extending the MMB format beyond 511 disks

Post by TobyLobster »

hoglet wrote:
Tue Sep 28, 2021 7:49 am
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
Last edited by TobyLobster on Tue Sep 28, 2021 9:04 am, edited 1 time in total.
User avatar
TobyLobster
Posts: 170
Joined: Sat Aug 31, 2019 7:58 am
Contact:

Re: Extending the MMB format beyond 511 disks

Post by TobyLobster »

dp11 wrote:
Tue Sep 28, 2021 7:37 am
Slightly faster, by moving some of the carry setting and clearing.
Nice!
User avatar
BigEd
Posts: 4446
Joined: Sun Jan 24, 2010 10:24 am
Location: West Country
Contact:

Re: Extending the MMB format beyond 511 disks

Post by BigEd »

TobyLobster wrote:
Tue Sep 28, 2021 8:50 am
dp11 wrote:
Tue Sep 28, 2021 7:37 am
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
Posts: 1332
Joined: Sun Aug 12, 2012 9:47 pm
Contact:

Re: Extending the MMB format beyond 511 disks

Post by dp11 »

BigEd wrote:
Tue Sep 28, 2021 9:29 am
TobyLobster wrote:
Tue Sep 28, 2021 8:50 am
dp11 wrote:
Tue Sep 28, 2021 7:37 am
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 ? :)
User avatar
hoglet
Posts: 10598
Joined: Sat Oct 13, 2012 7:21 pm
Location: Bristol
Contact:

Re: Extending the MMB format beyond 511 disks

Post by hoglet »

TobyLobster wrote:
Tue Sep 28, 2021 8:44 am
hoglet wrote:
Tue Sep 28, 2021 7:49 am
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
Last edited by hoglet on Tue Sep 28, 2021 11:28 am, edited 2 times in total.
User avatar
TobyLobster
Posts: 170
Joined: Sat Aug 31, 2019 7:58 am
Contact:

Re: Extending the MMB format beyond 511 disks

Post by TobyLobster »

hoglet wrote:
Tue Sep 28, 2021 10:54 am
Dave's: 26 bytes (+1 for the TAX)
Nice!
User avatar
hoglet
Posts: 10598
Joined: Sat Oct 13, 2012 7:21 pm
Location: Bristol
Contact:

Re: Extending the MMB format beyond 511 disks

Post by hoglet »

TobyLobster wrote:
Tue Sep 28, 2021 11:15 am
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
User avatar
sweh
Posts: 2566
Joined: Sat Mar 10, 2012 12:05 pm
Location: New York, New York
Contact:

Re: Extending the MMB format beyond 511 disks

Post by sweh »

His it been decided that the 511-concatenated version is the direction forward? Or are people still making up their minds?
Rgds
Stephen
User avatar
hoglet
Posts: 10598
Joined: Sat Oct 13, 2012 7:21 pm
Location: Bristol
Contact:

Re: Extending the MMB format beyond 511 disks

Post by hoglet »

Here's the final version of the DIV/MOD 511 subroutine with comments:
https://github.com/hoglet67/MMFS/blob/5 ... .asm#L6498
Coeus wrote:
Tue Sep 28, 2021 2:50 am
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
User avatar
hoglet
Posts: 10598
Joined: Sat Oct 13, 2012 7:21 pm
Location: Bristol
Contact:

Re: Extending the MMB format beyond 511 disks

Post by hoglet »

sweh wrote:
Tue Sep 28, 2021 12:33 pm
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
User avatar
BigEd
Posts: 4446
Joined: Sun Jan 24, 2010 10:24 am
Location: West Country
Contact:

Re: Extending the MMB format beyond 511 disks

Post by BigEd »

Sounds great!
User avatar
robcfg
Posts: 144
Joined: Sun Dec 30, 2018 6:23 pm
Contact:

Re: Extending the MMB format beyond 511 disks

Post by robcfg »

Ok, I’ll add support for it during the weekend.
User avatar
tricky
Posts: 5832
Joined: Tue Jun 21, 2011 9:25 am
Contact:

Re: Extending the MMB format beyond 511 disks

Post by 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
Posts: 2360
Joined: Mon Jul 25, 2016 12:05 pm
Contact:

Re: Extending the MMB format beyond 511 disks

Post by Coeus »

hoglet wrote:
Tue Sep 28, 2021 12:37 pm
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?
User avatar
hoglet
Posts: 10598
Joined: Sat Oct 13, 2012 7:21 pm
Location: Bristol
Contact:

Re: Extending the MMB format beyond 511 disks

Post by hoglet »

Coeus wrote:
Tue Sep 28, 2021 7:57 pm
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
User avatar
hoglet
Posts: 10598
Joined: Sat Oct 13, 2012 7:21 pm
Location: Bristol
Contact:

Re: Extending the MMB format beyond 511 disks

Post by hoglet »

Comment is fixed now (on the large_mmb_support2 branch)
User avatar
sweh
Posts: 2566
Joined: Sat Mar 10, 2012 12:05 pm
Location: New York, New York
Contact:

Re: Extending the MMB format beyond 511 disks

Post by sweh »

hoglet wrote:
Tue Sep 28, 2021 8:31 pm
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
Rgds
Stephen
User avatar
sweh
Posts: 2566
Joined: Sat Mar 10, 2012 12:05 pm
Location: New York, New York
Contact:

Re: Extending the MMB format beyond 511 disks

Post by 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!
Rgds
Stephen
Post Reply

Return to “8-bit acorn hardware”