DarkerLine: The Blog

Here’s an idea for displaying images quickly, potentially to nearly the whole screen (obviously, nothing can beat RecallPic, but that has the disadvantage of using picture variables).

Like text sprites, this technique uses part of the pixels displayed by Text(, except this time it’s the bottom row. The advantage of this method is that by displaying multiple characters at a time, you can draw a whole row of pixels at once - filling the screen that much more quickly.

The good news that I only came up with today is that it’s actually possible to come up with any combination of pixels this way: the key is the list L and finance N characters, which don’t have a padding of blank pixels on the sides. In fact, using only four characters: space, period, [, and the list L, any image can be drawn.

I haven’t had the opportunity to experiment further, because my calculator is critically low on batteries. But in fact, this isn’t the way to draw characters, because filling a row with fewer wider tokens is more efficient in terms of speed and memory. Ideally, you’d be using all (or nearly all) of the possible tokens.

One limitation is that the top five rows of pixels (and an additional column on the right) are off-limits. You could probably add regular text at the top of the screen to get around this (that is, to pretend that it’s a feature, not a limitation).

Results hopefully to come: screenshots, a program to save the screen to a string, and an attempt to use this method for tilemaps.

As always, I bring you the very best in meaningless trivia about internal workings of the TI-Basic parser.

TI-83 Basic’s “memory leaks” are caused by the way loops and If:Then blocks were parsed — each time such a beast is encountered, the parser pushes relevant data to a stack and waits for an End. A Goto that skips over a few Ends will wreak havoc with this process because the top of the stack will never get cleared.

TI-68k Basic deals with this problem by not allocating any memory for blocks in the first place. Instead, each End command (such as EndWhile, EndFor, EndLoop, etc.) stores an offset to its parent While, For, Loop instruction — the math is done during tokenization. If the End is encountered, the parser uses this offset to look at the head of the loop and see if it’s time to stop looping. But if some Goto happens to exit the loop in the middle, no harm done.

I guess this is a lesson to people planning to write interpreted languages. A preliminary “tokenization” step can really save a lot of trouble.

#include "ti83plus.inc" .db tFullScreen, tColon, tYOff, tColon, tPlotOff, tColon
.db tGFormat, tGridOff, tColon, tGFormat, tAxisOff, tColon
.db tZoomStd, tColon, tZInt, tEnter

.db tDelVar, tO, tChs, t1, t4, tStore, tA, tEnter
.db tChs, t2, t6, tStore, tB, tEnter
.db t2, t9, tStore, tC, tEnter

.db tRepeat, t0, tEnter
...


Wikipedia is defines a one-way function as a “function that is easy to compute but hard to invert.” There are multiple well-known cryptographic functions reputed to be one-way, but they’re usually annoying to compute on a TI-83 series calculator, because they tend to rely on modular arithmetic with very long integers. So with the admission that I’m not really creating anything new, here is an idea for a somewhat weaker one-way function that’s easily computable on a calculator.

The idea is that storing a number N to rand, and then generating a random number, is very easy. But given the random number, you’d have to do a brute-force search using something like this code (on a computer) to find out what N must have been. This is basically impossible to do on a calculator.

Here is an example of using this method as a hash function for a password program.

New password:

randInt(1,E9→X
Input “New password?”,N
N→rand
DelVar N
{rand→LPASS
X→rand

Input password:

randInt(1,E9→X
Input “Password?”,N
N→rand
DelVar N
If min(rand=LPASS
Then
Disp “Correct!
Else
Disp “Wrong password!
End
X→rand

This method isn’t perfect because it ignores some digits of a too-long password, and passwords should be allowed to have letters anyway. You could write a getKey routine to fix that, though. As a side note, the first and last lines of code preserve randomness (if you didn’t do that, and used this in a game that depends on random numbers, they’d come out the same every time you entered the same password).

I’ve already pointed out (maybe not on this blog) that the TI-68k calculators have a quirky way of storing lists: since they’re stored as an expression, they can only be accessed sequentially (much like a linked list in “real” programming languages). There’s some consequences to this. For example, consider the following two routines:

:For i,1,dim(list)
: If list[i]=value
: Return true
:EndFor
:Return false

and

:Return product(list-value)=0

While the second routine is smaller, in no sane programming language would it be faster. In TI-68k Basic, it is: 3 times faster for only a 10-element list, and 12 times faster for a 100-element list (on average)! This is explained by the quirk in list access. In big-oh terms, the first routine is O(n²) whereas the second is O(n), since the product() command can go through the list just once and multiply everything together.

Moral: avoid For loops. Yeesh.

A discussion of factoring methods in my number theory class led me to believe that the continued fraction factorization method might be ideally suited to a number factoring program on the TI calculator. Consider: floating-point math and square roots are much more natural operations on a TI-83+ than the modular arithmetic heavily involved in most other factoring algorithms. And the numbers that can be represented in a floating point number aren’t going to require heavier machinery anyway.

Link to Wikipedia’s article on continued fraction factorization. Maybe, code to come?

• TI-68k Picture Editor
• Tunnel Racer (TI|BD sample program)
• A faster version of the above that scrolls 2 pixels at a time
• New, 18×18 sprites for Invasion on TI-92,TI-92+, V200 calculators

Now, to work on finishing up the more difficult parts of my list…

Edit: Interesting compatibility issue no one mentions: the dialogs on the widescreen calculators use a larger sized font - and as a result, not as much text fits into one Text instruction.

1. Buy a TI-89 Titanium (probably around $150) or a Voyage 200 (probably around $200) calculator.
2. Download Invasion. Edit for optimizations, for wide-screen compatibility, and possibly for bugs, release update.
3. Thoroughly enjoy being able to check what I’m writing on TI|BD without using an emulator.
4. No longer feel guilty about using aforementioned emulator.
5. Write a TI-Basic game for the 68k calculators (I’m thinking an RPG take on Betrayal)
6. ???
7. Become famous throughout TI community for my TI-Basic programming skillz.

(Point 5 especially is not set in stone yet, so don’t get your hopes up)

Okay, so I guess I lied in the other post and am now writing the 68k version of TI|BD relying purely on willpower and TiEmu. Go me.

I’m not yet ready to write the definitive article on TI-68k tokens, but it looks like no one’s considered tokens at all before me. Then again, many people just program in C.

Common knowledge: The calculator tokenizes programs the first time you run them, modifying the program until you edit it again. If you archived the program before this happens, though, the OS can’t writeback to Flash so the program stays unedited, and gets tokenized every time you run it.

Tokens are basically the same as they are with TI-83 family calculators, there’s not a whole lot to vary, in any case. They seem to be much more 2-byte than they used to be, but I guess that’s reasonable since there’s more commands. I’ve yet to discover if strings are not tokenized at all or tokenized in a different way (that would replace characters with separate ‘character tokens’) but good news is that lowercase letters don’t take up extra space like they did with the TI-83.

What’s annoying, though, is that variable names take up space that varies with the length every time you use them (as opposed to just making a table at the beginning of the program and indexing it which I suppose would be too complicated). So there’s a great incentive to use one-letter names in the final product because it saves a large portion of the size. Also, there’s an extra 1-byte penalty for having a multiple-letter name (a 1-letter var takes up 1 byte, but a 2-letter var takes up 3 bytes).

Update: I’ve figured out most of the ways of tokens. Though I still am missing some details, the TI|BD article should be reasonably complete. Enjoy!