String to Byte
Takes the first 3 (non 0) chars of a string and converts to byte.

Notes:
Leading letters are treated as zeros.
Following letters are treated as null.
If string has a value > 255, a is overflowed.

Inputs:
HL: Null terminated string location in memory

Outputs:
A: Byte

Code:


Example:

Code:

A now contains $F4, or '244' in decimal.

Related to the previous post, here's a heavily optimized string to byte, at 14 bytes. Same inputs, but output is in C instead of A. eZ80 only. Will give garbage results if a non-digit character is encountered or if the number is greater than 255.

Code:


And for one byte more, here's a version that will return when encountering any non-digit character, leaving HL pointing to that character.

Code:

For a Z80 compatible alternative (15 bytes):

Code:


EDIT:
If you want to stop on a non-digit input (so not just a zero-terminated string):

Code:

Mod HL
returns the remainder after division of H and L and puts it in H

NOTE: actually doesn't divide, but simulates modulus.

Code:

Code:

Optimizing for size, I would personally suggest A mod L -> A

Code:

It get the job done a lot faster, destroys no variables, and it is 4 bytes. To modify it so that it uses H instead of A, simply wrap the code with a ld a,h \ ... \ ld h,a

Code:

EDIT: As Runer pointed out, this will cause an infinite loop if L=0. If you can't guarantee this won't happen, then use this H mod L -> H routine:

Code:

I have two neat routines, pushpop and diRestore. If you want to preserve HL,DE,BC, and AF, then you can just put a call to pushpop at the start of your routine. If you want interrupts to be restored on exiting your routine, you can call diRestore at the top of your code.

They both mess with the stack to insert a return routine on the stack. For example, when your code calls diRestore, then an ret will first return to the code to restore the interrupt status, and then back to the calling routine.


Code:


Code:

EDIT: calc84maniac pointed out that 'inc sp' can be dangerous without first disabling interrupts. I've reorganized the diRestore accordingly.

32-Bit Endian Swap (eZ80)

Swaps the byte order of a 32-bit value stored in EUHL. Can be adapted to work with other register combinations as well.


Code:

The ClearHorizLine routine here never got updated, so I took a stab at it, writing a routine for black, white, and inverted horizontal lines. In mine, they all use a common subroutine, but if you take just the white+subroutine, it is 32 bytes smaller (25%), and all combined take 25 bytes over the original.
(NOTE: I edited the original routine to use `rla` instead of `rl a` to get these results.)

Code:

I am going to continue editing this post if I come across other optimizations.

EDIT: Here is an optimized version of Ashbad's itoa_8 routine. It's much faster and less than half the size:


Code:


EDIT: Optimized the above itoa_8 routine more. Here are some more number-to-string routines:
uitoa_8
Converts an 8-bit unsigned integer to an ASCII string.

Code:


itoa_16
Converts a 16-bit signed integer to an ASCII string.

Code:


uitoa_16
Converts a 16-bit unsigned integer to an ASCII string.

Code:

Here are some routines that I've added to the repository:

fixed88_to_string
Uses the itoa_8 routine in the previous post to convert an 8.8 fixed-point number to a string.

Code:


sqrtA
This is a very fast, unrolled routine to compute the square root of A.


Code:


sqrtfixed_88
An unrolled, fast 8.8 fixed-point square root routine. Uses the above sqrtA routine.

Code:


ncr_HL_DE
Computes 'HL choose DE' in such a way so that overflow only occurs if the final result overflows 16 bits.

Code:

Masked Sprite
Earlier in the thread, Kerm offered a masked sprite routine. Fallen Ghost made some improvements, making it a smaller and faster and taking care of a minor bug, but at the cost of using the shadow registers (which needs interrupts off in many cases).
I optimized Fallen Ghost's routine, saving another 4 bytes and making it a little faster:

Code:

However, the reason they had to resort to the shadow registers was due to the sprite format. Instead of keeping the mask and the sprite data in two different chunks of memory, you can interleave them and avoid having to calculate another pointer. Doing it this way, I was able to save 17 more bytes and make it even faster:

Code:


We can save even more if we don't have to rotate in '1' bits into the mask, but this requires us to use a non-traditional masking method (but better in my opinion). We can OR the mask, then XOR the sprite data. This actually gives us an additional option for masking, too. Instead of black/white/clear, we can get black/white/clear/invert. See the 'Notes' section in the code below for the rules for generating a sprite:

Code:

In these two routines, note that I organize it with data first, then mask. In many cases, it could be cheaper for other operations if you put it in mask-data order. Since we are using the index registers to get the data, it's easy enough to swap the formats

---

Big Sprites

I also made some "bigsprite" routines! These do have clipping, too. First, they use some common subroutines for computing masks and performing most of the clipping and shifting:

Code:

Then you can draw a big sprite with OR logic:

Code:

Or draw with XOR logic:

Code:

Or draw with AND logic:

Code:

Or draw with Erase logic:

Code:

Or draw with Overwrite logic:

Code:


EDIT: Formatting and added bigsprite routines

Here is a useful routine! It is a scrollable menu that can have multiple titles, but works on the graph screen.

Feel free to use any of these!

Scrollable Menu With Multiple Headings

Code:


In my test, for example, I define these:

Code:


And I include the following routines for getkey and rectangle drawing, and converting ints to a string:

Code:


And I call it with:

Code:


It's a lot of overhead if your project doesn't need those rectangle routines or the getkey routines, but, you can modify those to use the built-in routines (it's just smoother this way). Either way, check out the example:


EDIT: Updated to define if there is padding above the text or not. Here is a screenshot of using the large font (save bandwidth, don't need a gif for this one )

The scrollable menu looks great!

sqrtHLIX
This is a 32-bit integer square root routine. It uses the unrolled sqrtHL routine at the bottom of this post as a subroutine. Note that this routine makes use of the undocumented SLL instruction, and so you might need to modify it for some devices. You can replace it with scf \ rl * at the cost of one byte and 4cc.

Code:

This routine outputs a remainder, which is useful to have on hand if you want to build higher precision routines. The two routines combined use 260 bytes in total, but that's the price of quick maffs.

Here is a neat circle routine that I made:

Code:

The really cool feature about this is that you can define a custom plot routine pointed to by IX, so it isn't TI-specific, and you can do all sorts of wonky things like:
Draw 2x2 pixels:


Code:


Or draw a circle whose "pixels" are circles:


Code:


EDIT: I inlined some subroutines because there was no reason to have them called. It was a waste of clock cycles and space!

EDIT: Have a separate, filled rectangle routine!
Note that if you pass the same arguments as the regular circle routine, this only draws the inside part and skips the border.

Code:

Here is an example screenshot of when I used an inverted horizontal line routine:

I have two routines that I am proud of and thought they'd be useful!

---

Binary Search
Binary Search is an efficient way to search through sorted data. Regardless of the data, the core of the algorithm is the same, so I made a routine that is the core algorithm!
All you have to do is pass a pointer to a routine in IX that compares two pieces of data

Code:

---

Heapsort
Heapsort is a clever and efficient sorting algorithm. Much like the Binary Search routine above, you pass IX pointing to a routine that actually interprets your data, so this can work on even your weirdest data format. IX points to a routine that either swaps two elements, or compares two elements (based on carry flag passed in).
NOTE: This also includes the heapify routine, used by heapsort. This might also be useful if you only need to arrange data into a heap structure, but don't need to sort.

Code:

Long post incoming!

---

rand_ti_float, rand10, rand5
I've long been annoyed about TI's implementation of rand. First, it is so. Freaking. Slow. Plus, the range is pretty limited in that the smallest number it returns is 1/2147483563 =4.6566...*10^-10. In fact, it an only return up to 2147483563 distinct values! (I'm basing this info off of this. It is for the 68k calcs, but I believe I read that the same algorithm is used on the Z80 calcs).

Anyways, I set out to make a better and faster rand for TI Floats after my breakthrough with the rand implementations in z80float. So here is the code:

Code:

I tried to be good with the comments on this code, so I won't go into depth with the algorithm. The main takeaway is that it needs rand10 to return A with a value on [0,9], and as long as the rand10 has a uniform distribution, then the float will return with a uniform distribution on [0,1).

So now we come up to the next challenge: generating a random integer on [0,9]. Well, that's simple! Just generate rand5, an integer on [0,4], then shift in a random bit:

Code:


Now we need to generate a random number on [0,4], and this is where the fun starts. There are two popular methods, and I'll try to illustrate why they fail. Suppose we have a True RNG that spits out a 0 or 1 with equal probability (for example, flipping a fair coin if that could exist). Just for ease of illustration, let's generate 4 bits and perform rand%5, a common technique. Well, with a True RNG, that means 4 values map to 0 (0, 5, 10, 15), and 3 values map to each of 1, 2, 3, and 4. So this means even with a true RNG, this method will bias the output to 0. Another popular technique is to essentially do int(5*rand). So in this example of generating a 4-bit number, we would do int((5*rand)/16). Well, we run into the same problem where it biases toward a value (in this case it is 0 again).

So how do you mitigate this? Well, if we add more bits, then we shrink the bias. For example with 8 bits, the rand%5 option only biases toward 0 by an extra ~2%. And if we went to 16-bit, the bias would be an extra ~.00763%. And honestly, that can be acceptable. But with only a finite number of bits, it'll never be truly uniform. So we need another approach, one that is finite.

It is worth noting, that if you had to choose from, say, 4 values, then you can always do that with exactly 2 bits. For 8 values, you can do it with exactly 3 bits. With 2^n values, you can do it with exactly n bits. These are finite processes and we like these. In fact, most of the best pseudo-random number generators are really good at providing "random" bits with uniform distribution. So we need a trick to take the ease of generating bits, and using that to make a finite process for rand5.

My approach basically looks at the binary expansion of 1/5, 2/5, 3/5, and 4/5.

Code:


So if we generate random bits and I get .001100, then a 0, then we know that no matter what all of the rest of the bits are, the number is less than 1/5, and so int(5*rand) is 0.

By applying similar logic to the rest of the values, we can guarantee a uniform distribution on [0,4]. But there are four cases where this process might continue forever, specifically the cases that are like ...00110011...., but lucky for us, this happens 4/inf= 0% of the time. In fact, on average it takes 4 bits before the algorithm can assert which value to return. The one caveat is that on the Z80, we generally don't have truly random numbers On the other hand, it is easy enough to generate pseudo-random bits with equal probability

So, without further ado:

Code:


If I use this as my rand routine (a fast xorshift+ generator), then generating a quality, random TI-float on [0,1) with uniform distribution seems to take under 13400cc. This translates to over 1100 TI floats per second at 15MHz). You can also heavily modify the rand5 routine to keep track of it's internal state (specifically HL [random bits] and B [counter]) and only call rand when HL runs out of bits. When I did this (and used a slightly faster RNG), I was able to get over 1960 random floats per second.

For reference, the OS _Random bcall can run nearly 71 times per second, which is about 15.5 times slower than the code above, and 27.5 times slower than a heavily optimized version.

rand8 (very fast)
I have a beautiful RNG. It is 47cc and 10 bytes.


Code:


Upon first inspection, that use of the R register might look like it is being used as a source of randomness, but it is in fact being used as a cheap counter. This leaves us in a very interesting position: If the R register happens to be random or chaotic in your use-case, then that is good! But if R just acts as a counter, then that is also good, because that is what the PRNG needs.

The basic trick is to combine a counter or LCG with an LFSR to smooth out the distribution of the LSFR. Since LSFRs are very fast, and R is a built-in counter on the Z80, we can combine them to make a very, very fast random number generator that is decent quality.

Now, there are some caveats. Due to the nature of the R register, this does not have a fixed cycle length. On average, it has a cycle length of 5592320 (meaning you could expect it to loop after every 5592320 numbers generated). The cycle length could be as low as 65535 (it is essentially just the LFSR), or as high as 8388480. If you wait for external input between calls, then you basically have a true RNG.

Here is a gif demonstration:

Another good use-case is fire animation! (sorry for the poor quality gif, it's really a lot smoother IRL)


EDIT: If HL is 24-bit, as in ADL mode on the eZ80, then your LFSR needs different taps (but in this case, it doesn't improve cycle length because we are still using H instead of UHL):

Code:


I have no idea what the speed is on the eZ80. 10 fetches, maybe?

EDIT2: this comparison might be a little easier to interpret:
(LFSR only)


(combined with R as a counter)

---

EDIT: (2020-07-23)
Apparently even an 8-bit LFSR combined with the R register does a great job at generating noise, so here is an even faster version (faster for the Z80, though this code also works on the eZ80):

Code:

Zeda, your prng routine is awesome!
(Here's something I made using it, ez80 calc compatibility)

(Packed) BCD to Binary, 2 or 3 digits (z80, no bcalls)

Don't know if anything like this has been posted yet, so here's what I came up with. Uses the Reverse Double Dabble algorithm for converting binary-coded decimal to standard binary. Any loops are unrolled for step-specific optimizations (and thus, overall, optimized more for speed than size). The 3-digit version is not exactly optimized, but the 2-digit version is (as best I can), and is presented in a form both with and without using shifts/rotations.

3 digits:

Code:


2 digits, using shifts:

Code:


2 digits, no shifting:

Code:


Some of the optimizations found for the 2-digit version could probably be applied to the 3-digit version.

If you can afford to use more registers, there is a snippet here that you might find useful: https://www.cemetech.net/forum/viewtopic.php?p=238223#238223

Code:


In my use-case, I was reading BCD bytes at HL and converting them to 8-bit ints. If you have the BCD byte in a register, it is easy enough to adapt:

Code:


(By my calculation, your last routine averages 91.824cc assuming all inputs are valid BCD.)

Your routine is pretty great when you can't destroy any RAM or registers except A, and I like that approach; I'm curious how well it can be optimized.