MinYMizer

A handler for maxYMiser .MYS and .MYV files, meant to limit itself to straightforward YM programming techniques (i.e. lightweight and portable).

Historical context

PSGs

In the late 70s, video games started to appear that needed sound. Two significant chips came out of this period:

GI's AY-3-8910, initially designed for the Intellivision in 1978, where it was used alongside other GI chips.

TI's TMS-9919, initially designed for the TI-99/4 in 1979, where it was used alongside other TI chips.

Both of those chips ended up used in environments beyond those of their original manufacturers, both in arcade machines and home machines.

The GI chip was notably in the Oric 1, MSX, Amstrad CPC, later ZX Spectrum models, and Atari ST. It's found in other machines, notably several JDM computers.

The TI chip found its way in the BBC Micro, the ColecoVision, the near-identical Sega SG-1000 (from where it found its way to the Mega Drive), the IBM PCjr, and, very late, the Neo Geo pocket.

MaxYMiser

As it turns out, the Atari ST, in which the AY-3-8910-based YM2149F is used, is a very powerful machine in comparison to the original Intellivision. Specifically, the ST is powerful enough to program the YM2149F thousands of times per second, up from dozens in less powerful machines, which makes it possible to combine chip capabilities in ways that create new waveforms, and even to play sampled sounds (with the matching memory usage). Those techniques had been used here and there back in the heyday of the Atari ST.

Around 2005, gwEm (Gareth Morris) started a project called maxYMiser that tried to extract the most of the YM2149F in the Atari ST, while remaining faithful to the chip's PSG characteristics, hence the name. Specifically, maxYMiser is not an Amiga-style sample-based tracker; its ability to handle sampled sounds is limited. At its peak feature set, maxYMiser takes over a significant part of the ST, using all of its timers and most of its CPU and RAM. The documentation hints that it's possible to write musics with so many effects that a plain ST can't play them back for lack of CPU power.

MinYMizer

As it turns out, while maxYMiser can go extremely far in pushing the AY-3-8910 / YM2149F to the limit of what the Atari ST can do, it can also be used without any of those advanced effects, in which can it is an excellent, fully-featured and flexible PSG music editor. However, the default maxYMiser playback routine is extremely heavy, somewhere around 50kB of code and data without the music itself. Also, while the source code is available, it is not under an Open Source license, and it relies on tools that explicitly disallow Open Source projects.

Furthermore, the maxYMiser file formats are somewhat inefficient and therefore heavy. A non-representative set of examples suggests that, for typical song, those formats might average to 120 to 200 bytes of data per second, or 15 to 20kB per song, which is acceptable on an Atari ST but can quickly get tight or infeasible on 8-bit machines. A cursory look into the formats suggests that lots of holes exist in the files that could be easily eliminated, and that there are likely opportunities for compression.

This present project leverages maxYMiser's editor and outputs, reprocesses the output files (in MYS and MYV formats for songs and voicesets respectively) into a tight documented format, and offers playback code under en Open Source license, with an eventual intent to offer players for other platforms, likely at least those that use Z80 CPUs.

The name of this project, minYMizer, is an obvious pun on maxYMiser, with an American spelling twist on top.

footnotes

Even though TI's and GI's PSGs were successful, and TI's matching video chip also spawned several families of successful chips, the CPUs that those companies originally used didn't go anywhere. TI's TMS9900 is a re-implementation of their minicomputer, while GI's CP1610 has some clear inspiration from the PDP-11 but is limited by its 10-bit opcodes, down from the PDP-11's 16. They were probably too expensive against 8-bit processors, and, by the time 16-bit architectures were realistic, too limited by their 16-bit address spaces compared to the 8086's 1MB and 80286's and 68000's 16MB.

Also, amusingly, on the one hand, Yamaha made their YM2149F almost identical to the AY-3-8910, which also ended up in several OPN chips including the one in the Neo Geo. But, on the other hand, Sega worked with Yamaha to expand the capabilities of the TI chips from the SG-1000 into the Master System. As a result, Yamaha ended up making chips from both families, and YM chips with relationships to both families exist side-by-side in the Sega Mega Drive.

File format constraints

The file format involved is built under two constraints:

• It must map back and forth to the maxYMizer file formats, within the constraints of portable PSG features (i.e. no reliance on timer-driven effects).
• It must be playable without having to be full decompressed in RAM. The buffers needed for decompression must be small compared to what full decompressed data would cost, small enough to run on a variety of hardware.
• Playback on the Intellivision is explicitly not a requirement for the most advanced formats, because of that machine's very limited RAM (1472 gross total, in practice between about 140 and 1400 depending on which system features are enabled). On Intellivision, the large ROM space (likely at least 48k words) allows for a lower compression ratio in order to save RAM.

Expanded format

The MXG format (MaXimized Groove) is a flat variant of the combination of MYS and MYV file, with no compression and no trimming, such that it has a fixed size.

• Signature: 8 bytes "MXGROOVE"
• File version: 4 bytes (major, minor, big-endian)
• Song length: 1 byte
• Song repeat: 1 byte
• Song speed: 1 byte
• Pad: 1 byte
• Song: 1024 bytes (256 * 4) at offset 0x10
• Patterns: 131072 bytes (256 * 64 * 8) at offset 0x410
• Instruments: 2048 bytes (32 * 64) at offset 0x20410
• Sequences: 32768 bytes (256 * 128) at offset 0x20c10
• Total: 166928 (163 kiB + 16 bytes) (0x28c10)

Compression

Initial notes

An initial look at musics created for current and past projects reveals the following information:

• By a huge majority, once gaps in the files are removed, the largest amount of data is in the patterns themselves. Song steps, instruments, and sequences combined represent less than 10% of the size of the files. Initial compression efforts beyond patterns are misguided.
• In turn, being able to decompress patterns in-place in real-time is important, because they might otherwise use 10kB decompressed (as an order of magnitude). Because they're read sequentially, LZ compression is very appropriate as long as patterns are compressed independently. -In those conditions, about 80% of pattern rows are covered by in-pattern LZ repeats. -Beyond that, typically more than half of literals are used only once, making them unsuitable for direct Huffman compression.

Exact numbers:

	Cloudy	VMAX cover	MoMeM	Plic Plic Ploc
Step bytes	78	60	36	51
Pattern bytes	11648	9856	4928	7168
Instrument bytes	108	180	84	108
Sequence bytes	408	580	288	286
LZ1 repeats rows	1430	1185	590	853
LZ1 sequences	200	268	112	166
Literal rows	234	223	114	171
Single literals	83	93	68	44
Reused literals	50	49	19	47
LZ2 repeats rows	1363	1071	545	783
LZ2 sequences	133	154	67	96
Literal rows	301	337	159	241
Single literals	74	68	56	36
Reused literals	59	74	31	55

Pattern compression

Main stream

Decompression of patterns is meant to follow the following pattern: The bit stream contains tokens from a Huffman table, and each token can refer to:

• An inline literal (for literals used only once), where the literal is then read from the bit stream. There's a single Huffman code for all such literals.
• A re-used literal (for literals that are used multiple times), where each such literal has its own Huffman code.
• A LZ repeat, where the Huffman code also encodes the length, and the distance is then read from the bit stream.

Main Huffman table

The main table contains a mix of literals (~50 bits, with potential for variable sizes) and repeat lengths (6 bits). Storing a fixed-width table is probably wasteful, to the tune of 6 bytes per possible LZ repeat length, i.e. possibly in the low hundreds of bytes. There is flexibility to build a near-canonical Huffman table here, alternating the various bits of data for each code length (i.e. all literals first, all repeat lengths after).

LZ lengths

Needs to be investigated for choices between 1-length repeats vs using literals. Does not change the actual format. Using literals biases the literals toward more shared (stored in Huffman table) and fewer isolated (stored as inline literals).

LZ distances

Needs to be investigated for repetitions, most probably can be stored in a separate Huffman table

Pattern line literals

In the range of 100 to 150 unique pattern rows. Naive storage is 7 bytes per row, resulting in ~1kB of naive data. In first approximation, this is not the largest contribution to pattern sizes and can initially be stored uncompressed. However, there's a high probability that individual fields can be stored into Huffman tables.

Handling of effects into Huffman tables remains to be investigated.

• Effect paramaters might theoretically be optimizable into separate Huffman tables, but there might be too few of those to justify the effort.
• Empty effects, which have no parameters, can most probably skip the parameter aspect entirely.
• Single effects vs paired effects. While the maxYMiser format can have 2 effects per row, effects are most often stored solo. It might be possible to store info into the first effect's Huffman table whether there's a second effect to read (i.e. a continuation bit).

Compression order

1. Process patterns into LZ77 tokens

• Try different lower bounds on repeat
• Put literals in a side table

2. Split literals between inline and shared

• Try different lower bouns of re-use

3. Generate Huffman tables
4. Minimize Huffman tables for storage
5. Encode tokens with Huffman tables

Literal pattern coding

Use canonical Huffman, method 2: store number of unused lengths to skip, range of possible lengths, number of codes of each length, followed by actual codes (whose number is determined from the previous count).

E.g. if codes range from 5 to 8 bits in length: store 4 as 4-bit number (meaning, skip 1 - 4) store 3 as 4-bit number (meaning, lengths range from 5 to 5 + 3 bits) store number of 5-bit codes as 5-bit number (offset by 1, there can't be 0), store number of 6-bit codes as 6-bit number (there can't be 64, because there wouldn't be any 5-bit codes), store number of 7-bit codes as 7-bit number store number of 8-bit codes as 8-bit number

It might be possible to reduce by a few bits, from knowledge of the possible number of values.

Canonical Huffman coding for LZ repeat lengths

Back-of-the-envelope numbers suggest that method 1 is better than method 2 for Canonical Huffman of LZ repeat length, as long as we only store code lengths for the symbols that are actually used.

-store the list of symbols present:

• 0, followed by 63 bits
• 1, followed by 16 groups representing 4 bits each (including zero-length)
  • 0 -> 0000
  • 1000 -> 0001
  • 1bbbe -> bbbe (where bbb is not 000)

-store the lengths of the symbols present:

• 0: lengths are 3 bits each, 2-9 (1 is uncommon but 9 is common)
• 1: lengths are 4 bits each, 1-16

-store the lengths, per bit size defined above

As a quick experiment, here are numbers on different music files. Most likely, groups of 4 works best because of 4:4 music, and EGroups of 4 (where 0001 is stored slightly shorter) because they match the 4:4 use case of a variable row followed by 3, 7, 15, 31 predictable rows.

	Cloudy	VMAX cover	MoMeM	Plic Plic Ploc	Avg
No groups	63	63	63	63	63
Groups of 3	72	57	48	54	57.75
Groups of 4	72	52	44	56	56
Groups of 7	65	58	44	65	58
Groups of 9	70	52	43	61	55.75
CGroups of 3	72	57	48	54	56.5
CGroups of 4	72	52	44	56	54.75
CGroups of 7	65	58	44	65	58
CGroups of 9	70	52	43	61	55.75
BGroups of 3	70	57	47	53	56
BGroups of 4	72	51	44	56	54.5
BGroups of 7	65	57	44	65	57.75
BGroups of 9	70	52	43	61	55.75
EGroups of 3	72	56	48	52	55.75
EGroups of 4	72	51	44	53	53.75
EGroups of 7	65	57	44	65	57.75
EGroups of 9	70	52	43	60	55.5

	Cloudy	VMAX cover	MoMeM	Plic Plic Ploc
Code lengths	3-9	2-9	2-8	2-8

Canonical Huffman coding for LZ inline literal

-stored as 4 bits, code length 1-16

-might not exist at all (if all literals are used multiple times)

Canonical Huffman coding for LZ numbered literal

Special handling of empty literal? (might not exist at all)

Canonical Huffman method 2 works better for this case: store the number of codes of a given length, with with a literal table matching that order.

Straightforward: -Store shortest length (1 to 16) -Store number of lengths (1 to 16)

For each length, store number of symbols that use that length

-First number can't be zero, because that's explicitly the first. -Later numbers can't be the max, because some of the namespace has already been allocated.

Adaptive? Figure out how many of a given size can still be stored, from what's already been inserted into the canonical table. Use a bit size that matches, on demand. This even takes care of the end condition, i.e. when the code tree is full.

Free Software

This is Free Software. In a nutshell, that means that you may use the software without any restrictions, that you may distribute it to others, that you may modify it in any way you want and distribute modified versions to others. Being on the Copyleft side of Free Software, you're required to give those same rights to others when you distribute that software to others, including the modifications you make. See the license file for details.

You might think of Free Software along multiple dimensions:

• Free Beer: you're not required to pay for it.
• Free Speech: software is a form of expression, as is what we do with it.
• Free Will: you are in control of what you do with that software, you don't need to ask me or anyone else for any permission. You decide how you use it, you decide how it gets modified to fit your needs, you decide how it gets maintained for you.
• Free Puppy: you might not have any upfront payment, but that doesn't mean that there won't be ongoing costs.
• Free Boat: the software comes with no warranty. You need to be prepared for the possibility that it might be useless or fail catastrophically.
• Free Toilet: everyone wants toilets to be clearn and free, but nobody wants to clean toilets for free. If you want that software to continue being useful for you, you need to expect that you might have to pay for that.

Licensing

Conversion code is AGPL

Playback code licensing still TBD, LGPL is a likely candidate

The requirement to mention maxYMiser when using songs created with it is NOT lifted by using this software, please acknowledge gwEm's work as per his request.

Legal

This code as provided is out of GDPR scope (no personal identifiers), out of CRA scope (no network connection), out of NIS-2 scope (not in any of the sensitive domains).

The original author recommends against using that code anywhere that would bring any such restrictions in scope, and should not be expected provide any support toward meeting the requirements of those restrictions.