samhocevar [Lexaloffle Blog Feed]

Pent8cle

Mon, 15 Apr 2024 01:02:35 UTC

Hi!

It’s been ages since I did anything for Ludum Dare. This time the theme was “Summoning”, so this is my attempt at a puzzle game where you need to complete a pentacle in order to summon whatever it is you summon. I did not spend too much time on this and could not find game mechanics that were both fun and challenging, so don’t expect anything great…

Left/Right arrows: browse runes (in select mode) or rotate rune (in placement mode)
Z/C: select rune (in select mode) or place rune (in placement mode)
X: cancel rune placement and return to select mode

Compo entry page is here.

pent8cle

by samhocevar

[Click to Play]

Insecure format string handling in export()

Thu, 22 Feb 2024 17:18:56 UTC

PICO-8 will gladly accept export("sfx_%x_%d.wav") because the string argument contains %d, but the format string is not sanitised and the SFX index will be caught by %x, and %d will then pick who knows what memory location.

Funny things can also happen with %s, %*s etc.; export("%s%s%s%s%s%s%s%s%s%s%s%s%d") is almost a guaranteed crash.

Combining short while and short if confuses parser

Thu, 01 Feb 2024 07:06:10 UTC

Here’s a simple example:

a=0
while(a<4) a+=1 if(a!=3) ?a
print('lol')

Expected output:

1
2
4
lol

Actual output:

1
lol
2
lol
lol
4
lol

Improved sin() and cos() precision

Sun, 21 Jan 2024 10:46:06 UTC

The sin() and cos() functions seem to be using some kind of lookup table at ¼ the number resolution, with clamping. It is easy to use linear interpolation instead and improve the precision of these functions by calling them twice:

function trig(f,x)
  local a, b = f(x & 0x.fffc), f(x | 0x.0003)
  return a + (b - a) * (x << 14 & 0x.c)
end
function xsin(x) return trig(sin,x) end
function xcos(x) return trig(cos,x) end

@zep I think PICO-8 could very well do this internally, as the extra cost seems negligible. The same goes with atan2(), especially since in that case it is significantly more difficult to do in PICO-8 user land.

precise_sincos

by samhocevar

[Click to Play]

atan2() picks wrong quadrant when dy=0x8000.0000

Sat, 20 Jan 2024 23:47:02 UTC

atan2(1,0x8000.0001) returns 0.25, as expected. However atan2(1,0x8000.0000) returns 0.75.

This is the kind of stuff that could be compiler-specific because 0x80000000 is a bit special, however I get this on both Windows and Linux (64-bit).

Fast sort function (97 tokens) / faster sort function (111 tokens)

Mon, 06 Jul 2020 16:04:51 UTC

Here is a simple implementation of merge sort in 97 tokens. It uses less PICO-8 CPU than anything else I’ve tried (with a caveat, see below).

A small benchmark comparing CPU usage, sorting an array of 200 random numbers:

this merge sort: 12% CPU
ce_heap_sort (casual effect’s heap sort): 12% CPU (but 191 tokens)
iqsort (dual-pivot quicksort by Felice): 74% CPU in degenerate cases (already sorted list), 10% CPU otherwise
zsort (quicksort by musurca): 125% CPU in degenerate cases, 18% CPU otherwise

Note that non-randomised quicksort suffers from very bad performance on quasi sorted lists, so the above benchmark does not represent what you would get in real life. Always test in your own application.

function sort(t, a, b)
    local a, b = a or 1, b or #t
    if (a >= b) return
    local m = (a + b) \ 2
    local j, k = a, m + 1
    sort(t, a, m)
    sort(t, k, b)
    local v = { unpack(t) }
    for i = a, b do
        if (k > b or j <= m and v[j] <= v[k]) t[i] = v[j] j += 1 else t[i] = v[k] k += 1
    end
end

In real life merge sort performs worse than e.g. quicksort because it suffers from poor locality of reference (cache misses), but in a high level language such as Lua this becomes meaningless.

To any computer scientist this specific implementation would be badly written and would appear to perform extremely poorly because {unpack(t)} effectively copies the whole array ~~n×log(n)~~ n times. However, in PICO-8 world this function is ridiculously fast because for the virtual CPU the operation is almost free. Use at your own risk because the actual CPU running PICO-8 will still perform the operations!

Another limitation: does not support arrays of more than 16384 elements because of the overflow in (a+b)\2. Just replace with (a/2+b/2)\1 if necessary.

Edit: here is a version that performs log(n) full array copies and is thus much lighter on the CPU. It is also about 10% faster. The drawback is that it’s now 111 tokens, but that’s still pretty good.

function sort(t)
  local function f(a, b)
    if a < b then
      local d = (b - a) \ 2 + 1
      f(a, a + d - 1)
      f(a + d, b)
      local v, j, k = { unpack(t, a, b) }, 1, d + 1
      local vj, vk = v[j], v[k]
      for i = a, b do
        if (not vk or j <= d and vj <= vk) t[i] = vj vj = v[j] j += 1 else t[i] = vk vk = v[k] k += 1
      end
    end
  end
  f(1, #t)
end

Wrong token count for signed constants

Tue, 09 Jun 2020 10:18:49 UTC

Here are a few token count discrepancies:

print(12)    -- 3 tokens
print(-12)   -- 3 tokens
print(~12)   -- 3 tokens
print(-~12)  -- 4 tokens
print(~-12)  -- 5 tokens
print(~~12)  -- 4 tokens

?12    -- 2 tokens
?-12   -- 3 tokens
?~12   -- 2 tokens
?-~12  -- 3 tokens
?~-12  -- 4 tokens
?~~12  -- 3 tokens

Also this inconsistent behaviour with spaces:

print(-12)   -- 3 tokens
print(- 12)  -- 4 tokens
print(~12)   -- 3 tokens
print(~ 12)  -- 3 tokens

Feature proposal: extend the PNG cart compression algorithm

Tue, 09 Jun 2020 09:33:38 UTC

I recently wrote a post about storing random data as strings in carts and studying the built-in compression algorithm. It led, among other conclusions, to the following two observations:

PICO-8 is not very good at compressing random strings that use more than 64 different characters; those get actually expanded by about log₂(n)/6. For instance a random string of length 1000 that uses 128 different characters will use 1000*log₂(128)/6 = 1167 bytes in the cart.
The new compression format is redundant and allows for sequences that are not needed. For instance 011 01111 001 and 010 0000001111 001 both encode a back reference of length 4 at offset -16.

Most other compression schemes have some sort of fallback mechanism when they are unable to compress a block. For instance the DEFLATE format (for zip or gzip) has non-compressed blocks. In the above thread I made a suggestion to extend the compression format in a similar way, but here I have a much simpler proposal:

010 00000 marks the start of a zero-terminated sequence of uncompressed bytes

This works because:

010 00000 never happens in a compressed stream; anything that would start with that sequence could start with 011 instead and be much shorter
the null byte is not allowed in the code
the overhead is only two bytes; it can be more efficient than the current format for some strings as short as 7 characters
it should be easy to adapt the existing compressor so that when it realises the last X bytes have compressed badly it backtracks and stores the bytes instead

Feature proposal: shorthand poke

Tue, 09 Jun 2020 08:41:47 UTC

I would like to propose the following syntax extensions to PICO-8 for symmetry with the shorthand peek operators. Basically it means treating the peek operators result as an lvalue:

@x = y     -- short for poke(x,y)
%x = y     -- short for poke2(x,y)
$x = y     -- short for poke4(x,y)

@x += z       -- short for poke(x, @x + z)
%12 |= %42    -- short for poke2(12, %12 | %42)
$x >><= 4     -- short for poke4(x, $x >>< 4)

Wrong token count for some operators

Mon, 08 Jun 2020 17:43:44 UTC

The following operators cost 2 tokens instead of the usual 1 for compound assignment operators:

\=
^=
>><=
<<>=
..=

edit: I confused >>>= and ^= in my initial post.

Parsing issues with short if() cause bugs

Sun, 07 Jun 2020 22:07:09 UTC

I’m writing a minifier and I still can’t really wrap my head around the parser.

Here are two similar snippets that differ only in whitespace and do not do the same thing:

> for i=1,2 do
>  if(i)print(i) end
> print(3)
1
2
3

> for i=1,2 do
>  if(i)print(i) end print(3)
1
3
2
3

Large P8 carts get corrupted (0.2.0i)

Wed, 27 May 2020 08:54:07 UTC

When attempting to load a .p8 cart that exceeds the 65535 character limit (one that may have been created by an external editor or tool), PICO-8 silently drops lines at the end of the cart and does not report errors. It then accepts to save the (now corrupted) cart when pressing Ctrl-S, overwriting the original file.

Here is a sample cartridge for testing purposes; notice that the last print() line disappears when loading it.

One more observation: sometimes, when the 65535 character threshold lies in the middle of a Lua statement, a loading error does appear. I have been unable to identify when exactly.

Small PNG carts get corrupted (0.2.0i)

Tue, 26 May 2020 17:09:53 UTC

I created a cart containing the following code:

print("hello")

Then in the shell:

save foobar.p8.png

If I close PICO-8 and reopen foobar.p8.png, I get gibberish in the code section:

Parsing inconsistencies

Tue, 19 May 2020 21:47:05 UTC

Due to the preprocessor parsing numbers differently than Lua, here are some issues:

Valid code (1e-3 is a valid number in Lua):

a=1e-3

Invalid code (1e-3 is parsed as 1 e - 3 by the preprocessor):

a+=1e-3

Invalid code (2b is an invalid number in Lua):

a=1+2b=3

Valid code (2b is parsed as 2 b by the preprocessor):

a+=1+2b=3

Unusual memory behaviour at 0x5f4c

Tue, 19 May 2020 08:55:25 UTC

Not sure if it is really a bug, but poking at the 8 bytes starting at 0x5f4c then immediately peeking will discard the two highest bits:

> p=0x5f4c poke(p,255) print(@p)
63

I know this is a special area and the memory is modified by the virtual hardware between frames, but no other location discards bits like that.

Infinite recursion in 0.2.0f bit shift operators

Tue, 05 May 2020 21:52:54 UTC

The new shift operator behaviour where a>>n returns a<<-n when n is negative causes an infinite loop and freezes PICO-8 when shifting by -32768:

?1<<-32768
?1>>-32768
?1>>>-32768

>>> not exactly the same as lshr()

Sat, 02 May 2020 13:43:57 UTC

shr(x,n) and lshr(x,n) have always handled shift values outside the 0…31 range in a peculiar way: negative values of n are treated like n&31, while values ≥ 32 always return 0 (or 0xffff.ffff for a signed shift).

But now the new >>> operator diverges from lshr by treating n ≥ 32 like n&31, so we get:

   1 >> 32 = 0
 shr(1,32) = 0
  1 >>> 32 = 1
lshr(1,32) = 0

edit: same with << which no longer behaves like shl()

Encoding random data in the code section

Fri, 01 May 2020 07:03:31 UTC

Just a few things I thought I’d share. Sorry if it’s gibberish and/or uninteresting to most people.

Many carts store extra data in the code section, most of the time inside strings. Some people will store structured data such as JSON or JSON-like data and let the PICO-8 compression mechanism deal with it, but you must have seen people who rolled their own compression mechanism and use custom formats such as modified base64 that takes advantage of the 59 “good” characters (i.e. the ones that needed only one byte of storage in the .p8.png format instead of two).

-- custom base64 data
local data = "e*!jfg57yfl+[7dmrin_bt#0/g6!1y68(.xh.ata_kn3j7!un_s+jn5..a)s8xi/ou0/{ff)ec}["

Such base64 data encodes 6 bits of information per character, and requires an average of 8.625 bits per character on the old format cartridge (pre-0.2.0). It means that this “alphabet” gave us about 5.565 bits of information per byte on the cartridge (8 * 6 / 8.625).

The new compression format is now charset-agnostic; there is no reason to use custom encodings and favour those 59 characters. We can therefore use standard base64 as far as only storage is concerned (when thinking about decoder complexity, using a contiguous alphabet would be smart):

-- base64
local data = "RpUpAUT80Jf6CQakfKLHz+1BSpUxFUYa/JDtdeAo4cyC1tHDx6gpazu0kdJqFdX+e4rMvfA+Ua0L"

This data still encodes 6 bits of information per character, but now requires an average of 8 bits per character on the new format cartridge, giving us exactly 6 bits of information per byte on the cartridge (better than the old compression method).

So I wondered: what about other alphabets? (of more or less than 64 characters)

Here are the theoretical results, assuming perfectly random data and ignoring the fact that the compression algorithm may emit back references:

Here are my conclusions:

the new compression algorithm always outperforms the old one for random data
starting from about 40, alphabet size no longer really matters (there are “peaks” around 48 and 112 but probably not worth exploiting)

In a future post I will study the effect of the back reference emission (which are rare on random data but non-negligible with small alphabet sizes), but I’ll wait for 0.2.0e to be out since Zep mentioned on Twitter that he fixed something in the compression.

! undocumented

Mon, 20 Apr 2020 21:34:44 UTC

Not really a bug, but I accidentally discovered that '!' now gets replaced with 'self' at runtime, except when followed by '=':

> !ish = 42
> ?selfish
42

This is a bit confusing because in other languages, ! is an operator, whereas here it behaves almost like any other letter.

PICO-8 plugin for Tiled

Sat, 18 Apr 2020 16:44:27 UTC

I made a tiny plugin that lets Tiled load .p8 cartridges, edit the map section, and save them back without breaking the code or other sections. Works great for me, so I hope you may find it interesting!

Available on GitHub: https://github.com/samhocevar/tiled-pico8

Here is what it looks like with a dark theme and the grid color set to white:

Update 2021/02/20: The plugin was ported to JavaScript for compatibility with all OSes. Requires a preview version of Tiled (1.5.0) for now.