10 ms·
JSON parser written in 6502 assembly language
- timmattison 6y agoThe opening line in the README.md is worth clicking through for.
- sfg 6y agoIt is excellent.
- plorntus 6y agoI wonder if this is faster than GTA Onlines microtransaction JSON file parser.
- Waterluvian 6y agoI think a hypothetical Json parser written in Conway's Game of Life would be faster.
- keanebean86 6y agoRockstar could get a performance boost by bundling powerpoint: https://youtu.be/uNjxe8ShM-8 https://youtu.be/uNjxe8ShM-8
- dnsco 6y agoThis just made my day. Thank you.
- oblio 6y agoOr they could use this: https://github.com/xoreaxeaxeax/movfuscator https://github.com/xoreaxeaxeax/movfuscator See this presentation, too: https://www.youtube.com/watch?v=R7EEoWg6Ekk https://www.youtube.com/watch?v=R7EEoWg6Ekk
- yholio 6y agoDev: Please see the some powerpoint slides that explain how we can bundle an improved JSON parser that will... PHB: Bundle PowerPoint?! That's... genius! I can see a bright future for you here. Dev: ...
- matheusmoreira 6y agoIs it a matter of if? I wonder how many times faster it is...
- JdeBP 6y agoIf you want to measure it, you first need to work out how to load 10MiB of JSON into the 6502's 64KiB address space. Or test it rewritten for a KimKlone. (-: * https://www.laughtonelectronics.com/Arcana/KimKlone/Kimklone_memory_commentary.html https://www.laughtonelectronics.com/Arcana/KimKlone/Kimklone...
- vidarh 6y agoBank-switching like the KimKlone does would be possible to support via a cartridge on the C64. Alternatively - though I don't think any of them have been pushed to that size, the CBM REU's did memory transfers fast enough that they actually were faster than using the CPU (because they could use every available bus-cycle for the actual data transfer). So you would likely need custom/new hardware, but in terms of how, it's a solved problem.
- boomlinde 6y agoThat's all right, this is an event driven parser so at no point does it actually need a full representation of the document in addressable memory to parse it.
- sim_card_map 6y agometa
- notretarded 6y agoThank you for your contribution
- kristaps 6y agoTime complexity O(R*)
- caslon 6y agoIs the 6502 the peak of hobbyists writing assembly? I think it fills a fantastic niche of being well-documented while also not being completely terrible to write by hand.
- gfody 6y agothere's something incredibly comfortable about being able to view the instruction set along with affected flags and supported address modes in its entirety on something about the size of an index card
- caslon 6y agoThe elegance of that time is something unfortunately missing from modern software.
- the_only_law 6y agoI don't even know hoe x86 experts got there. I'm constantly learning about all sorts of strange instruction that look like random strings and perform seemingly odd calculations.
- caslon 6y agoIntel has kept their ISAs roughly-consistent with each other since 1972. Of course, in doing this, they have created a behemoth. You can't make something smaller when your goal is eternal (in)consistency.
- zozbot234 6y agoRISC-V has its own ISA summary card, AIUI. Plot twist: there are no address modes (since it's a load-store architecture, all loads and stores are explicit) and no flags to keep track of (since compare-and-branch instructions are used instead of flags, to make higher-performance implementations easier).
- zimpenfish 6y ago
- anta40 6y agoKinda misleading title, because if you take a look at the code: https://github.com/ppelleti/json65/tree/master/src https://github.com/ppelleti/json65/tree/master/src It's only the core (https://github.com/ppelleti/json65/blob/master/src/json65.s https://github.com/ppelleti/json65/blob/master/src/json65.s) which is written in asm. The rest are C. Seems neat anyway, let's fire a 6502 emulator :)
- lifthrasiir 6y agoThe leading paragraph mentions "It's time to write a JSON parser in 6502 assembly language?" so I figured out everything in C is supplementary ;-)
- RantyDave 6y agoCame here to say that. Also we have cbor which is "json for embedded". But, hey! it's still pretty hardcore. Not something I'd be doing.
- uKVZe85V 6y agoAccording to github https://github.com/ppelleti/json65 https://github.com/ppelleti/json65 C 47.1%, Assembly 40.4%, Perl 9.4%, Haskell 3.1%. Yes, it actually contains perl and haskell code [0]. [0]: https://github.com/ppelleti/json65/blob/master/run-tests.pl https://github.com/ppelleti/json65/blob/master/run-tests.pl https://github.com/ppelleti/json65/tree/master/tools https://github.com/ppelleti/json65/tree/master/tools
- naters 6y agoThe "Library organization" section [1] explains that the json65.s file is the core of the library and the only code necessary to build the library. The additional C code provides a handy tree structure and a callback to pass to the parsing engine. However, because SAX is a callback-oriented parsing method, you can design your own data structure and write your own callback functions and do without this tree structure. The additional C code provides similar nice-to-haves, such as string pool interning, a function to print out the aforementioned tree structure, and a wrapper function to parse json from a file. [1] https://github.com/ppelleti/json65#library-organization https://github.com/ppelleti/json65#library-organization
- userbinator 6y agoAs surprising as it sounds, this might actually have a practical use --- with the 6502 being such a tiny core it ends up in a lot of obscure MCUs, possibly with IoT-ish/toys/etc. high-volume low-cost applications, and the seeming unwillingness of a certain subset of developers to use more efficient binary protocols, I wouldn't be surprised if someone does end up needing to get a 6502 to parse JSON. The 8051 and Z80 fill similar roles today --- when even the cheapest ARM core is too expensive.
- deleted 6y ago[deleted]
- colejohnson66 6y agoI just can’t imagine anyone who knows how to write assembly being one of the “JSON everything” people. But who knows. Not knocking JSON. Just thinking it wouldn’t be the right thing for this situation.
- mpoteat 6y agoEnter a JSON wrapper format for specifying assembly applications, compete with a NodeJS transpiler toolchain a la Babel. Seriously though, it's been a while since I've had to work with assembly or IDA but JSON is great as an interoperable data format. Sure, it's not maximally efficient, but what needs to be?
- lambda_obrien 6y ago> it's not maximally efficient, what needs to be? I'm guessing most things written for a 6502
- QuesnayJr 6y agoEmacs had to add JSON parsing to its C core to get reasonable performance when using JSON for interprocess communication.
- 6y ago
- peanut_worm 6y agoI am a lowly JS dev so forgive my ignorance but what exactly would it be parsed to? Assembly doesn’t have a concept of objects/hash tables, does it?
- minitoar 6y agoThis particular parser is intended to be called from C.
- sircastor 6y agoMy only experience with the 6502 is writing ASM for the NES. So I had no concept for how this would work.
- nineteen999 6y agoYou could use the CC65 compiler to compile C to 6502 assembly, although, even C generally uses a (relatively) obscene amount of memory on an 8-bit system. https://www.cc65.org/ https://www.cc65.org/
- lifthrasiir 6y agoIts core, implemented in 6502 assembly, is a streaming parser and emits a series of events to signal the boundary of objects or arrays and atomic values. For example `[1, {"a": true}]` will emit something like `abegin; number 1; obegin; okey "a"; true; oend; aend; end`. There is a supplementary C library that parses this into a recursive structure (you will typically need to do the linear search for keys then).
- peanut_worm 6y agoOh okay that makes sense. Thank you for explaining.
- ddoolin 6y agoBut is the JSON allowed to have comments? Very cool. Things like this make me admire people's patience.
- debo_ 6y agoASM, Perl, Haskell, and C all in one JSON parser. I got a kick out of reading this.
- rsj_hn 6y agoI would be careful to use this without validating and normalizing the unicode prior to passing it to this parser. Not saying that it's a bad design, but big flashing security warnings should be used so that people are aware that higher order unicode can and usually is normalized prior to JSON parsing (so that, e.g. producers that use full width quotation marks can have their json parsed correctly rather than not have the double quotes recognized) and this consumer can only handle fully normalized and validated UTF8
- CorpOverreach 6y agoI'm pretty sure no one is running mission/security-critical applications on a 6502.
- 211BSD 6y agoIt won't and should not be used in mission-critical applications, but just for extra fun, one may still want it to be as correct as possible. Right now I'm writing a cryptography library in PDP-11 assembly while investigating tools for its formal verification. Cryptoline looks like a promising candidate.
- rsj_hn 6y agoI always assume the worst! There will be some auto engineer trying to backport some functionality and will be googling "JSON Assembly" and will port this code.
- uKVZe85V 6y agoNever underestimate the longevity of systems, since new systems tend to be built on top of old systems. Though I do not know any, I'm pretty sure in 2021 there *are* mission/security-critical applications running on 6502s in a number of places in the world.
- Tor3 6y agoThe 6502 is one of the few processors validated for embedded medical devices. From https://www.westerndesigncenter.com/ https://www.westerndesigncenter.com/ ".. the 65xx microprocessors protect millions of lives annually within embedded heart defibrillation and pacing systems. " Can't get more mission-critical than that I suppose..
- patrick451 6y agoThe first paragraph of the readme is definitely worth a click! One of the best of seen.
- zamalek 6y ago> JSON65 supports incremental parsing, so you can freely feed it any sized chunks of input, and you don't need to have the whole file in memory at once. It boggles the mind that we have a high quality JSON parser that supports this on such a constrained system, where many of the high-level language libraries that run on massively faster hardware don't.
- lifthrasiir 6y agoBecause it is slower? Many performant JSON parsers optimize parsing by batching, so it isn't constrained by possibly much slower I/O bottleneck. Also JSON65 itself does have a string size limit of 255 bytes.
- speedgoose 6y agoIt's because there is no need for that and when you need to load a JSON that doesn't fit in memory you can use better dedicated tools.
- shultays 6y agoIt supports that because it is a constrained system
- bilekas 6y ago> strings are limited to 255 bytes > However, there is no limit on the length of a line, I'm a little confused by this.. Can someone explain ?
- theblazehen 6y agoI think the size of a json string would be limited, eg {'key': 'string that is limited'}
- ddingus 6y agoAny entity within a line needs to be 8bits in length or less. Probably due to the index registers being 8 bits themselves. LDA (pointer to string), X
- user-the-name 6y agoFor comparison, here is a single-file JSON parser I wrote for resource constrained systems, but which more targets things like 32-bit Cortex M systems rather than 8-bit: https://github.com/DagAgren/SmallJSONParser https://github.com/DagAgren/SmallJSONParser
- bollorior 6y agoIf you asked me to write a JSON parser in 6502 assembly, I would put the fairly short and unambiguous JSON grammar into lex and yacc to get a parser in C, then compile that to 6502 assembly. Then maybe glance through the assembly code, although I doubt very much that I know anything about assembly that the compiler doesn't. Of course the author is a highly skilled person who also did this for his enjoyment. But am I missing some way in which what he did would be more than incrementally better than what I would do? Aren't these tools pretty much as good as the best humans at solving this problem?
- m463 6y agoThere are some assembly languages that are pretty straightforward to write code in, and if you're organized it is not too onerous a task. That said, 6502 is probably one of the LEAST featureful assembly languages I've ever used. I remember finding out it didn't have an ADD instruction - you clear carry, then add with carry.
- tyingq 6y agoProcessors like the 6502 aren't considered very C friendly for a variety of reasons, but mostly because the register size isn't big enough for the most common data types like int or char *. You often end up with terrible ASM.
- bollorior 6y agoInteresting, thank you.
- PostThisTooFast 6y agoCool. In the ‘90s I wrote a 6502 assembly program to convert my Atari Touch Tablet drawings into Windows BMP files. I then had to fire up my Atari modem, and an IBM-compatible running a BBS program and transmit them through the phone lines of my parents’ house. A couple of them wound up in a technical-architecture manual for clients of a Big-6 firm.