Talk:BytePushCore

From Esolang
Jump to navigation Jump to search

This is brainstorming. All reasonable and un-reasonable input is welcome.

This text will be nice-ified little by little. Kai-zen.

maybe we could have a text drawing font stored in ROM? TheCoderPro (talk)

So... Now there are some simple BytePusher example programs. Mine (user:Javamannen's) are big & ugly monstrosities written in C. But at least they show some things that can be done with BytePusher. User:Zzo38 was a bit more clever with his lightweight Munching Squares (3 kilobytes, written in PUSHEM assembler). One consideration with BP is speed vs size. You need the big tables for speed, which brings us to the subject of Runtime Table Generation, which will be needed for almost all non-trivial BP programs.

BytePusher (and ByteByteJump) depends on opcode tables to simulate a "normal" instruction set. The small 1-operand tables (pages) take up 256 bytes each, and the big 2-operand ones (banks) take up 64 KiB. Let's say you need 32 2-operand tables to approximate the functionality of a "normal" 8/24-bit CPU. That means 2 megabytes program filesize, and that's just for the opcode tables! Not so minimalist anymore, eh? But what if we started with a very small set of basic 1-operand tables, and expanded these into a full instruction set at runtime, before executing the "actual" program? Then we could decrease the overhead for the tables to just a few kilobytes.

So I was thinking, maybe start with these 256-byte opcodes as our initial building blocks:

Name Description
Increase by 1
Decrease by 1
Bitshift left 1 step
Bitshift right 1 step Arithmetic / logical? Both?
Is Zero 1 if 0, 0 otherwise
Is Negative 1 if ≥ 80h, 0 otherwise
A ? B : C Ternary conditional operator. Select one of two values depending on a boolean. First store the 2 values at table index 0 and 1, then do the lookup.
Constant Identity function. Table[x] = x. This will probably be needed since BP has no other way to copy an immediate value.

That's about 2K for the initial tables. You can probably shrink this set even more, but let's start with these, and optimize later.

This whole process should not take more than a few seconds at program initialization, so as not to annoy the user too much. Let's say 5 seconds is acceptable (if you show the user some kind of progress meter or a simple intro). Then you have 0.15625 seconds per table = 9.375 frames per table = 9.375 instructions per table index (since a table is 65536 bytes, and we execute exactly that many instructions per frame). So, is that enough cycles? I don't know. The tough ones would be multiplication/division/remainder. But that's only 3 tables out of 32, so maybe it could work out.

The first logical step would probably be to generate addition and subtraction tables. Once you have these, it's easier to generate something more complex like multiplication.

Putting the opcode banks at the end of memory (E00000-FFFFFF), on Zzo38's suggestion. This way we don't have to do any code relocation.

What is a "reasonable" expanded instruction set? Suggest / discuss. Below is the preliminary opcode list V0.03. Now thinking maybe dedicated carry/borrow tables are not that essential? Can be done with relational operators. E.g. if Result < (either X or Y) --> Carry (only need to test the result against either X or Y). Also: if X < Y then Borrow. Correct me if I'm wrong! Also included ZZo's suggested tables (see talk page):

Opcode Name Description
E0XXYY ADD XX+YY
E1XXYY SUB XX-YY
E2XXYY AND XX (bitwise AND) YY
E3XXYY OR XX (bitwise OR) YY
E4XXYY XOR XX (bitwise XOR) YY
E5XXYY CMP Compare XX with YY. 00 if equal, 01 if greater, FF (-1) if less (where XX and YY are unsigned)
E6XXYY SH Shift XX by amount of YY (where YY is signed and XX is unsigned) (Some wasted space here. Repeated 16 times (only 4 useful bits for Y))
E7XXYY MUL (Unsigned) multiplication XX*YY.
E8XXYY MULH (Unsigned) multiplication XX*YY (high byte).
E9XXYY-FFXXYY More to come... DIV/MOD etc. BUT ... Let's not build too many air castles! Let's first try to get some basic stuff like addition/subtraction/AND/OR/XOR *actually working*.

Source language: going with Zzo38's PUSHEM (keep up the good work!). I have to read up on this language.

We don't need no addercation

Um, we don't actually need an ADD table, just a SUB table, unless we REALLY need every cycle we can squeeze. The idea is that you calculate x - (0-y) to get x + y - it CAN be done! --Ben Russell 21:59, 18 October 2010 (UTC)

  • That's true. Although, BP isn't exactly a speed monster ;) so you might actually need every last cycle. But a program should really only generate the tables it actually needs. --Javamannen 14:12, 19 October 2010 (UTC)

Also, my coding method is also pretty bad, not sure how it compares with Javamannen's coding but it basically involves a few helper functions wrapped around a file object in Python. --Ben Russell 21:59, 18 October 2010 (UTC)

  • Well, that's a nice bonus from BP being so simple: you can use practically any source/generator language. Just bake in some helper functions to get a single self-contained source file. No special libraries needed, just file I/O. --Javamannen 14:12, 19 October 2010 (UTC)

I might make my own macro lang. Then again, I might not. Who knows.

Perhaps there could be a borrow-after-sub table? I'm just not sure how to do carry-after-add though but I think it could be done from that. --Ben Russell 21:59, 18 October 2010 (UTC)

  • There are many ways to skin a cat... --Javamannen 14:12, 19 October 2010 (UTC)

A different way to skin this cat

My initial thought was to write BytePushCore in Zzo's PUSHEM assembly language and have it be some sort of language standard. The thing is, everybody has their own way of doing things and their own language preferences. The programs written so far are in C, PUSHEM and Python. That's 3 different languages for 3 different people. It's relatively easy to hack your own micro-assembler and include it directly in the sources. Perhaps it's more natural to view BP simply as a binary platform, a machine, with ".BytePusher" files as the lowest common denominator, and not worry about standardizing it on a higher level?

Still, it would be nice to have some sort of standard "cross-platform API": tables 'n' stuff that can be relied upon no matter what source language you're working with. This could be achieved by having BPC be a sort of standard binary "ROM" image instead, one that every compliant BP VM must include. Actually not a ROM since it's writeable; just an area at the top of RAM which is pre-filled with some potentially useful values. The VM would load the ROM image file from disk before loading the actual program. If a big enough program were loaded from disk, it would simply overwrite the "ROM" area. The image could contain some commonly needed ALU tables, a fixed-width font, some useful "system routines" like fast memcopy/fill, maybe sprite/blit routines, stuff like that. Since it's just normal RAM, if a program had no need for the BPC stuff it could use that memory for other purposes; the full 16 MiB would still be available.

Advantages

  • No runtime generation needed. No init delay, better user experience
  • Guaranteed binary compatibility across all platforms and source languages. This actually depends on an important condition: There must only ever be A Single Version of the ROM image. If we f**k that one up we'll have to live with it. If we started releasing different "improved" versions / patches, BP would eventually enter the same fragmentation hell as every other previous platform in history. A BP game created today must be guaranteed to run on any compliant machine, now and in 100 years (yeah, I know, by 2012 we'll all be gone =)

Disadvantages

  • You need to distribute the ROM image with every VM. So the file shouldn't be too big. I'm thinking 2 MiB should be enough? That's equivalent to 32 big tables.

Black Boxes

You can combine the 2 above approaches: a ROM image which has some routines for dynamic table generation. But the main thing is that it should be neutral w.r.t programming languages. There should be a reference document that describes the ROM contents in plain english. System routines should be considered "black boxes". It doesn't really matter in what source language the routines were originally programmed. Once it's finalized into the binary BPC image, all you need to know is what each routine does and how to call it.

Loading/saving snapshots

The way it works now

  • Saving: up to and including the last non-zero byte (you can save more if you want to, but it's pretty pointless).
  • Loading: zerofill everything after the last byte of the program file.

The way it would work with a ROM image

I'm assuming a 2 MiB ROM size here (I'll call it "ROM" even if it's technically incorrect).
The initial memory state, let's call it S, would be:

  • Zeros from 000000 to DFFFFF
  • The ROM image from E00000 to FFFFFF

Then it would work like this:

  • Saving: up to and including the last byte which is different from the corresponding byte in S (you can save more if you want to, but again, it's pretty pointless).
  • Loading: fill everything after the last byte of the program file with the corresponding values in S (alternatively, initialize the memory state to S first, and then load the file)


Relocating the actual program should not seem necessary, the banks can be generated at the end of memory instead of at the beginning, and not requiring relocation. The pages can be created using PUSHEM immediately after the program code and the addresses can be automatically placed in the code correctly. --Zzo38 19:52, 10 October 2010 (UTC)

Yeah, that seems easier. --Javamannen 20:37, 10 October 2010 (UTC)

I can suggest some more banks that can be possibly included:

  • Shift XX by amount of YY (where YY is signed and XX is unsigned)
  • Compare XX with YY, 0 if equal 1 if greater -1 if less (where XX and YY are unsigned)
  • Multiply XX by YY
  • Calculate remainder of dividing XX by YY

Also if you have any suggestions or questions about PUSHEM, I would like to know. --Zzo38 18:53, 11 October 2010 (UTC)

Added your suggested tables to the preliminary list. But let's not over-plan this... I guess my first little(?) PUSHEM project will be to generate a 64K addition table. I should probably just shut up until I have that one working =) --Javamannen 21:37, 12 October 2010 (UTC)

Vote: should BytePusher have a standard "system ROM"?

And, if so, how big should it be?
"System ROM" actually means a section at of RAM prefilled with useful data.
Cast your vote! Please sign.
The 3 people who contributed so far (myself (Javamannen), Zzo38 and Ben Russell) have 2 votes each.
Everyone else has 1 vote.

Options:

  • Who cares?
  • No ROM is needed.
  • 64 KiB
  • 128 KiB
  • 256 KiB
  • 512 KiB
  • 1 MiB
  • 2 MiB
  • 4 MiB
  • 8 MiB
  • 16 MiB

--Javamannen 12:44, 20 October 2010 (UTC)

I have another suggestion: Have it an option depending on the file extension or command-line argument, if set it will copy the ROM data to the end of RAM, otherwise the RAM will be filled only with the contents of the file. You can then have "plain mode" and "Core mode", and you can use your preference when writing the program (and can have it different for different programs). My suggestion is a compliant BytePusher VM need not support Core mode, and if you want to run a Core mode program on VMs that do not support it, you can use a separate program to convert a Core mode binary into a plain mode binary if necessary. BytePusher is just a machine specification, it doesn't specify standard ROM and therefore a compliant VM is not required to support a standard ROM. Core mode binaries can use the ".BytePusherCore" extension, while plain mode binaries use ".BytePusher" extension, by default. A include file can be made for PUSHEM to create macros for Core mode. If there are any contests, you can then have separate contests for plain mode and Core mode! Here are a few ideas of how VMs can implement this feature:

  • If the extension is ".BytePusherCore", generate the data and copy it to the end of RAM before loading the program binary.
  • If the extension is ".BytePusherCore", search for a file called "Core.BytePusherROM" and if it exists, copy the contents of that file to the end of RAM before loading the program binary.
  • Use an external program to combine them before loading the VM.

Compliant VMs then would be allowed to use any of these methods for loading standard ROM. I have another idea: Once the BytePushCore standard tables list is complete, rearrange them so that the most commonly useful ones are at the end. This way, a large program that overrides part of the BytePushCore area will be overriding the less useful tables, and the most useful tables shall remain in RAM. --Zzo38 19:06, 20 October 2010 (UTC)

I think that's a very elegant solution! None of the programs written so far need to be modified in any way, and people can safely continue to write programs which assume a zero-initialized memory. Actually, if the ROM is optional, then why not go crazy and max it out at 16 megs (OK, maybe leave the lowest 64K free)? After we have put the normal bread-and-butter stuff at the top of memory, there will still be lots of space left to fill with any weird esoteric stuff we can dream up =) Anyone can generate their own chunk of the ROM using their favorite source/generator language, and in the end we combine all the chunks into one big file.

As you said, it doesn't really matter how you get the ROM data into the VM's RAM (by loading the ROM file, by generating the data algorithmically, or by external preparation), as long as you get the same end result. But in case of doubt, the original raw binary ROM file should be the "gold standard".

--Javamannen 00:40, 21 October 2010 (UTC)

OK, have been thinking some more on this. Here's my current mindstate:

  • We have 2 filetypes:
    • ".BytePusher" (programs or "apps") and
    • ".BytePusherROM" (ROMs).
  • No special Core mode. Anyone can make their own ROMs.
  • A program may require a certain ROM to function correctly, or it may be intended to run on the "bare metal". This information must be published by the program developer. It's like specifying which OS the program runs on.
  • A ROM, like a program, can be any size up to 16 megs.
  • The initialized memory looks like this:
    • If a ROM is selected, it will be located in the upper part of memory. The lower part of memory will be zero-filled.
    • If no ROM is selected, the whole memory will be zero-filled.
  • A program is loaded at address 0, after memory has been initialized as per above.
  • When a snapshot is saved, the last byte which differs from the corresponding byte in the initialized memory will be the last byte of the file.

--Javamannen 05:31, 21 October 2010 (UTC)

Hmmm...This is starting to look too complicated! =/
The current spec is super simple. There's a single well-defined memory image file format, and a single set of well-defined criterions for VM compliancy. It's "just a machine". By extending the spec with more file formats or different levels of VM compliancy, things are already getting too confusing. It's the featuritis syndrome I guess, like that muLaw audio idea of mine. It can be very tempting to add "just one more thing" =)

If we were to have a standard ROM then it should really be a STANDARD ROM. Like it's burned into a virtual chip and soldered to the goddamn virtual motherboard or something =) Otherwise things will just fragment. And since we already have some 10 programs and 3 VMs built on the current ROM-less spec, I'm feeling it's too late to change it now. I remember proclaiming the spec to be "written in stone". Guess I just have to stand by that.

Still, anyone is free to add new file formats and VM extensions/modifications (like Ben's interlaced blit mode and dynamic register updates (cool idea b.t.w)).

But it probably shouldn't be part of the BytePusher standard..

--Javamannen 13:58, 21 October 2010 (UTC)

I agree. There should be no STANDARD ROM as part of the BytePusher specification. Other "add-on" specifications would specify these things, and a compliant BytePusher VM needs not implement anything other than the spec that has been proclaimed "written in stone". BytePusher has no standard ROM; although, like other new VM features, it is possible to support some things. I plan to implement the following in my implementation: If the extension is ".BytePusher(text)", then if a file named "(text).BytePusherROM" exists it will load it at top of RAM before loading the program ROM at the beginning of RAM; otherwise, if the extension is ".BytePusherCore" it will generate the Core tables at runtime before loading the program ROM (this second way will be implemented once the BytePushCore specification is done). In case the extension is just ".BytePusher" or the ROM file does not exist, it will initialize in the standard BytePusher way. (In case of VMs that do not implement this, you can use an external program to combine two files together so that it can be loaded in the standard-compliant way.) I agree it shouldn't be part of the BytePusher standard.

The way in which a program may require a certain ROM to function correctly, or it may be intended to run on the "bare metal", and this information must be published by the program developer (like specifying which OS the program runs on) is sensible; my idea is simply that this information is specified by the file extension. (Operating systems are not part of the machine specification.)

--Zzo38 18:41, 21 October 2010 (UTC)

All of this sounds sensible to me. Including the name of the required ROM in the file extension seems like a good idea, but may I suggest a slightly different naming convention? Instead of "ProgramFile.BytePusher(ROMFile)", we could use the form "ProgramFile.ROMFile.BytePusher" (in analogy to e.g. "File.tar.gz").

--Javamannen 22:52, 21 October 2010 (UTC)

Further thoughts about the naming convention...
If we go with the one I suggested above, the basic file extension will still be ".BytePusher", and will be recognized as such by VMs which only support the basic spec. An attempt by a basic VM to run a ".(RomName).BytePusher" file could result in strange program behavior, since there will only be zeros where the program expects the ROM data to reside. A well-behaved program should therefore start by testing if the ROM data is actually there (e.g. if address FFFFFF is nonzero), and if not show the user some kind of error message ("No ROM found" or something).

--Javamannen 06:11, 22 October 2010 (UTC)

Ah what the heck! Doing a bit of a U-turn here... =)
When you think about it, the above is really just a file naming convention and a very simple loading mechanism to be able to combine 2 different files directly in the VM, as a convenience and to get smaller filesizes. Why not include this in the VM spec then, at least as a "recommended practice"? Of course this convention doesn't apply to all systems, e.g. if there's no filesystem available. All that needs to be changed is a few lines of code in the loading/saving functions of our 3 respective VMs. And as Zzo already mentioned you could always pre-merge the 2 files in an external program instead. It's really no big deal.

So... If there are no strong objections I'll add this to the VM spec as soon as possible. We gotta move on to the more interesting stuff, like the Core tables =)

--Javamannen 16:25, 22 October 2010 (UTC)

This is getting ridiculous. I feel like Bart Simpson, forced by Ms. Krabappel to write on the blackboard:
I WILL NOT CHANGE THE BYTEPUSHER SPEC.
I WILL NOT CHANGE THE BYTEPUSHER SPEC.
I WILL NOT CHANGE THE BYTEPUSHER SPEC.

I must look like a total idiot now =D

--Javamannen 17:54, 22 October 2010 (UTC)

I agree with you. YOU SHOULD NOT CHANGE THE BYTEPUSHER SPEC. YOU SHOULD NOT CHANGE THE BYTEPUSHER SPEC. YOU SHOULD NOT CHANGE THE BYTEPUSHER SPEC. The ROM combining would be a separate specification and completely optional. And for the reasons you specified, I do not like the naming convention "(base-name).(extra-ROM-name).BytePusher", my naming convention would work better, for the reasons you have specified. (Again, any compliant BytePusher VM does not even have to know about these naminv conventions or about extra ROMs or anything like that; it is an optional feature that you can add, like other optional features that other people program into their own BytePusher VM implementations, such as pausing and so on.) The Core tables is like an operating system, and a machine specification doesn't include operating systems! (Filenames are not part of a machine specification either.)

A well-behaved program need not check for ROM (it is optional); rather, the programmer can include information with the distribution (using my filename convention, or any other way), and if the user does not follow the instructions it is not meant to work correctly.

My suggestion, the BytePushCore ROM can be whatever size necessary, after defining the draft BytePushCore specification, you can rearrange them so the most useful ones are at the end of memory (so that the loaded program overwrites the less useful ones).

--Zzo38 22:18, 22 October 2010 (UTC)

You're right, your naming convention has the advantage that there's no possible conflict with the original ".BytePusher" format. The only problem I see with it is that you get a proliferation of new file extensions: ".BytePusherCore", ".BytePusherThis", ".BytePusherThat"... =)

But there's actually a very simple solution to this:

  • We leave the original spec and its ".BytePusher" format alone (I finally got that into my head =)
  • Instead we create a new Level 2 standard file format ".XBytePusher" which uses the ".tar.gz"-style naming convention I suggested above. The "X" would stand for eXtended or maybe eXtensible.

This gives us the best of both worlds:

  • No possible naming conflict with original ".BytePusher" files, and
  • No proliferation of new file extensions

Examples:

  • Extended program "MyProg" running on bare metal will be "MyProg.XBytePusher"
  • Extended program "MyProg" requiring ROM "MyROM.BytePusherROM" will be "MyProg.MyROM.XBytePusher"
  • Extended program "MyProg" running in Core more will be "MyProg.Core.XBytePusher"

Thinking out loud... The XBytePusher spec could also include other stuff like a common VM extension mechanism. For example, anyone who creates a new VM extension could publish its specification in a central database (maybe just a simple Wiki table on an Esolangs page), and then other VM implementors would have the option to implement the same extension according to that published spec. We could also have a database of VMs and which extensions they implement. An XBytePusher program file could include information on which, if any, extension(s) the VM needs to implement to run it.

And you're right about the size of the BPC. No need to specify in advance.

About filenames and file formats not being part of a machine spec: That's technically true. Had I been really strict I shouldn't even have specified the the ".BytePusher" format or the load/save mechanism in the original spec. But you gotta do some compromises between hardware and software considerations. I mean it's not really a 100% strict low-level hardware specification, more like a hybrid software/hardware one.

--Javamannen 00:52, 23 October 2010 (UTC)

I like that ".XBytePusher" filename scheme. You can have VM extensions sort of like how NES/Famicom ROM files can have different mappers (but not quite the same thing).

However, for the extensible BytePusher, it would be the same format (normally, although some VM extensions might do things differently) and there is no need (or sense) for the "extended program running on bare metal". A standard program has the ".BytePusher" filename extension, if you wanted to use ".XBytePusher" for a program that is still compatible with normal BytePusher, you would give it instead the extension "..XBytePusher" (with two dots, meaning the name of the VM extension is blank).

If a VM extension name not recognized by a VM implementation, the VM can check for a corresponding ".BytePusherROM" file and load it at the end of RAM (but having the program have priority in the overlapping parts), and display an error message about "Unknown VM extension type" if the file is not found. (For some of the extensions (such as BytePushCore) a ROM file will be sufficient to make extensible BytePusher VMs not supporting that VM extension to be able to support it; but for future VM extensions that might or might not be the case (depending on what the people who create the new VM extension decide).)

The VM extension database can include columns "Name" (the part between the dots of the filename), "Category/Type" ("ROM" or "Other", although later on more types might be added), "Specification" (link to specification), "Implemented" (yes or no). The other table of the VM extension database is the list of BytePusher VM implementations, which can include columns "Name" (name of program), "Programming Language" (programming language it is implemented in (only if source code is available)), "Operating system" (operating system(s) the program runs on, if applicable), "Extensions" (list of VM extensions supported, can include things in parentheses like "(ROM)" meaning it will try extra ROM files if it is an unknown type, and can be blank if it supports only standard BytePusher; while if it says "Core" that means BytePushCore is supported without an external ROM file), "Test" (testing the program to make sure of compliance), "Program" (link to get program).

All of this stuff means:

  • A Core mode file (with extension ".Core.XBytePusher") can be converted to run on a BytePusher VM not supporting extensible BytePusher by simply combining a ROM file.
  • If you are downloading BytePusher files over FTP, you can see by the filename which VM extensions (if any) are required.
  • The file format remains simple.

The general idea of implementing such a conversion program could be as follows (obviously this is not a complete program): 

@ @<Do the conversion@>= {
  @<Figure out the filenames@>;
  @<Load the extra ROM file at the top of memory@>;
  @<Load the program file at the bottom of memory@>;
  @<Write the output file@>;
}

--Zzo38 03:29, 23 October 2010 (UTC)

Lots of interesting ideas there Zzo. But I think we're getting way ahead of ourselves here. It's so easy to get lost in higher and higher levels of abstraction, so let's go back to the absolute basics for a moment. The machine specification tells us that there is 16 MiB of RAM available. That's about all it should say on the matter. How those 16 MiB get initialized is really none of the spec's business. Even the ".BytePusher" file format is an abstraction (although a very minor one) on top of the "bare metal", and shouldn't even be part of the machine spec. It's just one of many possible ways to get some raw data into RAM. Hopefully there will eventually emerge some defacto standards for how things should be done. But let's forget all about the naming conventions and file extensions for awhile, and just get started with the Core tables! Everyone can start adding their own candidate tables to the list. No need to worry about redundancy or ordering in the beginning. When we feel we have a large enough set of candadate tables we can start discussing which tables to include (and where) in the final ROM file.

--Javamannen 06:21, 23 October 2010 (UTC)

Correct, let's get more started with the Core tables. One note about them: For things like the SH table that have some unused bits, you can use the extra bits for other things, such as: In the SH table use one of the extra bits to switch it to a "bit test" mode to test if a bit is set or not, which can be used to check which combinations of buttons pushed. And then you can have less space wasted.

Here are some ideas of tables:

  • Division
  • Carry/overflow
  • Rotate
  • Common subroutines
  • Bit test
  • Sine wave
  • Modulo
  • Fonts
  • Bank of all zero
  • Square root
  • Line drawing

--Zzo38 07:24, 23 October 2010 (UTC)

Retrieved from "https://esolangs.org/w/index.php?title=Talk:BytePushCore&oldid=84208"