Difference between revisions of "User:Rowett"

From LifeWiki
Jump to navigation Jump to search
Line 12: Line 12:


=== Goals ===
=== Goals ===
# It should be text based so easy to share, post to forums, Discord etc.
 
# It should be text-based so easy to share, post to forums, Discord etc.
# It should be easy to implement
# It should be easy to implement
# It should be fast to decode
# It should be fast to decode
Line 21: Line 22:
<tr><th colspan="3">Attainment</th></tr>
<tr><th colspan="3">Attainment</th></tr>
<tr><td bgcolor=#c0c0c0>Goal</td><td bgcolor=#c0c0c0>Rating</td><td bgcolor=#c0c0c0>Notes</td></tr>
<tr><td bgcolor=#c0c0c0>Goal</td><td bgcolor=#c0c0c0>Rating</td><td bgcolor=#c0c0c0>Notes</td></tr>
<tr><td>Text based</td><td bgcolor=#00f000>High</td><td>Not web safe</td></tr>
<tr><td>Text-based</td><td bgcolor=#00f000>High</td><td>Not web safe</td></tr>
<tr><td>Easy to implement</td><td bgcolor=#f0f000>Medium</td><td>JS implementation is 1000 lines of code</td></tr>
<tr><td>Easy to implement</td><td bgcolor=#f0f000>Medium</td><td>JS implementation is 1000 lines of code</td></tr>
<tr><td>Fast to decode</td><td bgcolor=#00f000>High</td><td>2-state decode 5x faster than RLE</td></tr>
<tr><td>Fast to decode</td><td bgcolor=#00f000>High</td><td>2-state decode 5x faster than RLE</td></tr>
Line 47: Line 48:
The RLE format is widely adopted, vaguely human-readable, and simple to implement.
The RLE format is widely adopted, vaguely human-readable, and simple to implement.


URLE isn't.
The URLE format is not.


=== Example Savings ===
=== Example Savings ===
Here are some examples of patterns showing a comparison between RLE and URLE file size:
Here are some examples of patterns showing a comparison between RLE and URLE file size:


Line 90: Line 92:


==== Count ====
==== Count ====
In run length encoding each symbol can be prefixed by an optional count defining the number of repetitions for the symbol. A count of 1 is omitted. The count is encoded as decimal digits (ASCII character <b>48 "0"</b> to <b>57 "9"</b>).
In run length encoding each symbol can be prefixed by an optional count defining the number of repetitions for the symbol. A count of 1 is omitted. The count is encoded as decimal digits (ASCII character <b>48 "0"</b> to <b>57 "9"</b>).


==== 2-State Cell Encoding ====
==== 2-State Cell Encoding ====
For 2 state patterns URLE will encode 5 cells into a single character. An end of row character is not required since it can be encoded with the 5 cells. If the row width is not a multiple of 5 then extra cells are guaranteed to be state 0.
For 2 state patterns URLE will encode 5 cells into a single character. An end of row character is not required since it can be encoded with the 5 cells. If the row width is not a multiple of 5 then extra cells are guaranteed to be state 0.


Line 98: Line 102:


==== Multi-State Cell Encoding ====
==== Multi-State Cell Encoding ====
For multi-state patterns the state numbers are encoded in base 32. If the state is >= 32 then the 32s digit is encoded from ASCII <b>63 "?"</b> to <b>70 "E"</b> representing 1x32 to 7x32.
For multi-state patterns the state numbers are encoded in base 32. If the state is >= 32 then the 32s digit is encoded from ASCII <b>63 "?"</b> to <b>70 "E"</b> representing 1x32 to 7x32.


Line 105: Line 110:


==== Dead Cell Groups ====
==== Dead Cell Groups ====
URLE encodes specific runs of dead cell groups into single characters.
URLE encodes specific runs of dead cell groups into single characters.
Longer runs will be multiples of these groups and reduce the [[#Count]] accordingly.
Longer runs will be multiples of these groups and reduce the [[#Count]] accordingly.
Line 127: Line 133:


==== Repeated Rows ====
==== Repeated Rows ====
URLE efficiently encodes repeated single or double rows as well as copies of rows seen earlier in the pattern.
URLE efficiently encodes repeated single or double rows as well as copies of rows seen earlier in the pattern.
<table border=1 cellspacing=0 width=500>
<table border=1 cellspacing=0 width=500>
Line 138: Line 145:


==== End of Pattern ====
==== End of Pattern ====
URLE uses a single character to mark the end of the pattern. This character is optional and is primarily used so comments can be added after the pattern definition.
URLE uses a single character to mark the end of the pattern. This character is optional and is primarily used so comments can be added after the pattern definition.
<table border=1 cellspacing=0 width=500>
<table border=1 cellspacing=0 width=500>
Line 143: Line 151:
<tr><td>End of Pattern</td><td><pre>&gt;</pre></td></tr>
<tr><td>End of Pattern</td><td><pre>&gt;</pre></td></tr>
</table>
</table>
Note that the URLE format does not use ASCII character <b>33 "!"</b> which is the RLE end of pattern character. This is to make if easy for decoders to differentiate between the formats.
Note that the URLE format does not use ASCII character <b>33 "!"</b> which is the RLE end of pattern character. This is to make it easy for decoders to differentiate between the formats.


==== Multi-state Alternate Encodings ====
==== Multi-state Alternate Encodings ====
For some multi-state patterns better compression can be obtained by compressing state by state rather than with all states at once.
For some multi-state patterns better compression can be obtained by compressing state by state rather than with all states at once.


Line 161: Line 170:


==== Whitespace ====
==== Whitespace ====
The encoder does not add whitespace (spaces, tabs or newlines) to the encoding apart from a final newline after [[#End of Pattern]].
The encoder does not add whitespace (spaces, tabs or newlines) to the encoding apart from a final newline after [[#End of Pattern]].


Line 166: Line 176:


=== Software Support ===
=== Software Support ===
There is a prototype implementation of URLE in LifeViewer. Press Ctrl-E to display metrics on compressing the current pattern in RLE and URLE.
There is a prototype implementation of URLE in LifeViewer. Press Ctrl-E to display metrics on compressing the current pattern in RLE and URLE.



Revision as of 09:29, 14 June 2021

  • Real name: Chris Rowett
  • My location: United Kingdom

LifeViewer

Author of LifeViewer, a scriptable pattern viewer and editor used here on the Wiki, the Forums, Catagolue and other places. A list of recent enhancements and fixes can be found in the Release Notes.

URLE

URLE is an experimental text-based compression format for pattern files with 2 to 256 states.

Goals

  1. It should be text-based so easy to share, post to forums, Discord etc.
  2. It should be easy to implement
  3. It should be fast to decode
  4. It should provide on average twice the compression of RLE

The table below shows ratings against these goals:

Attainment
GoalRatingNotes
Text-basedHighNot web safe
Easy to implementMediumJS implementation is 1000 lines of code
Fast to decodeHigh2-state decode 5x faster than RLE
2x the compression of RLEHigh> 4x for some patterns

Advantages

URLE format in almost all cases creates a smaller representation of a pattern than RLE format.

It's especially good at compressing 2-state patterns where typically it creates a file 1/3 of the size of the RLE format.

For patterns with more states (up to 256) it typically creates a file 1/2 the size of the RLE format.

For very small patterns it compresses similarly to apgcode in size.

Smaller pattern files mean:

  • Less storage required
  • Faster to transfer
  • Faster to decode
  • Larger patterns can be posted on the forum, Discord, etc.

Disadvantages

The RLE format is widely adopted, vaguely human-readable, and simple to implement.

The URLE format is not.

Example Savings

Here are some examples of patterns showing a comparison between RLE and URLE file size:

PatternWidthHeightStatesRLE sizeURLE size% of RLESaving
Exploratorium2297168927223K107K48%116K
Oscillator Stamp Collection30476492236K93K39%143K
Chaotic Checkerboard1241262158086334%15175

The following table shows a comparison between RLE and URLE file size for a 1024x1024 50% random fill pattern with the minimum and maximum number of states. A 50% random fill is typically a worst case since it doesn't allow long runs. The states were also randomized.

StatesRLE sizeURLE size% of RLESaving
2781K204K26%577K
2561379K1217K88%162K

It's also very good at compressing patterns with repeated consecutive single or double rows.

A 1024x1024 pattern filled completely with state 1 cells compresses as follows:

StatesRLE sizeURLE size% of RLESaving
26229100.16%6219

A 1024x1024 checkerboard pattern of state 0 and 1 cells compresses as follows:

StatesRLE sizeURLE size% of RLESaving
21039K4140.04%1039K

Format Specification (draft)

This section defines the format specification for URLE.

Note the specification is currently in Draft status and subject to change.

Count

In run length encoding each symbol can be prefixed by an optional count defining the number of repetitions for the symbol. A count of 1 is omitted. The count is encoded as decimal digits (ASCII character 48 "0" to 57 "9").

2-State Cell Encoding

For 2 state patterns URLE will encode 5 cells into a single character. An end of row character is not required since it can be encoded with the 5 cells. If the row width is not a multiple of 5 then extra cells are guaranteed to be state 0.

ASCII characters 63 "?" to 94 "^" are used to encode a 5 cell group with state values 00000 to 11111, and characters 95 "_" to 126 "~" are used to encode the same but at end of row.

Multi-State Cell Encoding

For multi-state patterns the state numbers are encoded in base 32. If the state is >= 32 then the 32s digit is encoded from ASCII 63 "?" to 70 "E" representing 1x32 to 7x32.

The units digit is encoded as the relevent ASCII character from 95 "_" for 0 through 126 "~" for 31.

A separate end of row character 58 ":" is required.

Dead Cell Groups

URLE encodes specific runs of dead cell groups into single characters. Longer runs will be multiples of these groups and reduce the #Count accordingly.

Dead Cell Group Encoding
ItemURLE
2 dead cell groups
"
2 dead cell groups + final dead cell group
#
4 dead cell groups
$
4 dead cell groups + final dead cell group
%
6 dead cell groups
&
6 dead cell groups + final dead cell group
'
8 dead cell groups
(
8 dead cell groups + final dead cell group
)
10 dead cell groups
*
10 dead cell groups + final dead cell group
+
12 dead cell groups
,
12 dead cell groups + final dead cell group
-
14 dead cell groups
.
14 dead cell groups + final dead cell group
/

Repeated Rows

URLE efficiently encodes repeated single or double rows as well as copies of rows seen earlier in the pattern.

Repeated Row Encoding
ItemURLE
Blank row
:
Repeated row
;
Repeated row pair
<
Copy of earlier row (count indicates row number)
=

End of Pattern

URLE uses a single character to mark the end of the pattern. This character is optional and is primarily used so comments can be added after the pattern definition.

ItemURLE
End of Pattern
>

Note that the URLE format does not use ASCII character 33 "!" which is the RLE end of pattern character. This is to make it easy for decoders to differentiate between the formats.

Multi-state Alternate Encodings

For some multi-state patterns better compression can be obtained by compressing state by state rather than with all states at once.

The encoder will try both methods and pick the smallest encoding.

Multi-state patterns encoded with all states at once are prefixed with two ASCII 48 "0" characters followed by #Multi-State Cell Encoding and finally #End of Pattern.

Patterns encoded state by state have a separate section for each used state in the pattern. Each of these sections starts with ASCII 48 "0", the state number, and then #2-State Cell Encoding.

After all used states are encoded in these sections the #End of Pattern is added.

State numbers are encoded in base 32. If the state is >= 32 then the 32s digit is encoded from ASCII 63 "?" to 70 "E" representing 1x32 to 7x32.

The units digit is encoded as the relevent ASCII character from 95 "_" for 0 through 126 "~" for 31.

Whitespace

The encoder does not add whitespace (spaces, tabs or newlines) to the encoding apart from a final newline after #End of Pattern.

The decoder will ignore any whitespace so it is fine to format the encoded string (for example to have 70 characters per line).

Software Support

There is a prototype implementation of URLE in LifeViewer. Press Ctrl-E to display metrics on compressing the current pattern in RLE and URLE.

Golly

Contributions to Golly:

Golly 4.1 (not yet released)

  • GUI
    • The cell population inside and outside of a selection can now be displayed in the status bar. Use Edit Preference: "Show selection population" to enable (default is disabled). To prevent lag the population is only displayed if the calculation takes less than 5ms while selecting or less than 500ms when the selection is complete.
  • Scripts
    • The Lua setoption and Python setoption commands now recognize "showcellborders" for showing or hiding cell borders when zoomed in >2x.
  • Rules
    • Fixed a bug in Larger than Life weighted neighborhoods with negative counts.

Golly 4.0

  • Rules
    • Added the new Super algo which supports [Rule]History and [Rule]Super rules.
    • Added support to Larger than Life algo for HROT format rules, B0 emulation, and many new neighborhoods:
      • Square neighborhoods:
        • Checkerboard
        • Cross
        • Euclidean (L2)
        • Gaussian
        • Hash
        • Saltire
        • Star
      • Hexagonal neighborhoods:
        • Aterisk
        • Hexagonal
        • Tripod
      • Triangular neighborhoods:
        • Triangular
      • All neighborhoods:
        • Custom
        • Weighted (with optional state weights)
  • Scripts
    • showinviewer.lua - LifeViewer now fills the browser window and resizes with the browser.
    • update-viewer.lua - downloads the latest version of LifeViewer to use with showinviewer.lua.
    • browse-patterns.lua - can now open the current slideshow pattern in LifeViewer.
  • Script commands
    • Added getgridtype command to get the current grid type.

Golly 3.4

  • Rules
    • Improved runtime performance of RuleLoader @TABLE rules.
  • Scripts
    • showinviewer.lua - launches the current pattern in LifeViewer in your default browser.

Golly 3.3

  • 3D
    • Major speed improvement to 3D.lua via custom-purpose ovtable commands.
    • Added cell history with fading.
  • GUI
    • Fixed a bug caused by simultaneous clicks of different mouse buttons.
  • Overlay
    • The optimize command now returns the minimum non-zero alpha bounding box of the clip.
    • The blend command now has a new faster blend mode ("blend 2") which should be used when the destination is opaque.
    • Improved the performance of the drawcells command.
    • Fixed a bug in and made several enhancements to the replace command.
  • Rules
    • Fixed a bug where the canonical form of Generations rules in MAP format was incorrect.

Golly 3.2

  • Rules
    • MAP rules now support base64 padding.
  • Overlay
    • The paste command now supports multiple locations for batch draw.
    • Added a new command lines which can draw multiple unconnected lines.
    • Added a new ovtable script command which provides a high performance table API for a subset of the overlay commands:
      • fill, get, line, lines, paste, rgba and set.
    • Added radio buttons to the oplus package.
    • Menu buttons now support custom colors and shadows.
    • Added timing function to the gplus package.
  • Bounded grids
    • Fixed a bug where patterns larger than bounded grids were not correctly clipped.
  • Scripts
    • credits.lua - animated credits that can be launched from Help > Credits page.
    • 3D.lua - improved generating and rendering speed, added depth shading and canonical rule format.

Golly 3.0

  • Rules
  • GUI
    • Drawing cell borders when zoomed in >2x is now controlled by a View Preference: "Zoomed cells have borders".
    • Significantly improved pattern rendering speed when zoomed in.
    • Added support for OpenGL 1.x
  • Overlay
    • Many improvements to the Overlay including the ability to play audio files.
  • Script Commands
    • Added getinfo command to get the comments from the current pattern.
    • Added getpath command to get the pathname of the current pattern.
    • The getevent command can now detect the release of a key.
  • Scripts
    • lifeviewer.lua - a Lua version of LifeViewer which runs in Golly using the Overlay (work in progress).
    • Co-wrote overlay-demo.lua which demonstrates most of the Overlay functions.
    • breakout.lua - a working game as a more sophisticated example of the Overlay functions.
    • browse-patterns.lua - allows you to browse through patterns in a folder (and optionally any sub-folders) manually or automatically.

Golly 2.8