A try to improve the line encoding. More...

Data Structures
struct	dlist_entry

struct	dlist_anchor

Enumerations
enum	dlist_entry_type { DLIST_NONE , DLIST_DIFF , DLIST_REP , DLIST_EQ }

enum	dentry_merge_status { DENTRY_MERGE_REC , DENTRY_MERGE_INA , DENTRY_MERGE_IMP }

Functions
static struct dlist_anchor *	dlist_anchor_create (void)

static void	dlist_list_clean (struct dlist_entry *d)

static void	dlist_anchor_destroy (struct dlist_anchor *anchor)

static unsigned	dlist_entries_count (const struct dlist_entry *d)

static struct dlist_entry *	dlist_edit_append (struct dlist_anchor *anchor, enum dlist_entry_type type, size_t offset, size_t cnt)

static struct dlist_entry *	dlist_center_find (struct dlist_entry *start, size_t cnt)

static size_t	dentry_encoded_overflow (unsigned sat, size_t value)

static size_t	dentry_rel_offset_calc (const struct dlist_entry *e)

static size_t	dentry_encoded_size_get (const struct dlist_entry *e)

static enum dentry_merge_status	dentry_merge_check (const struct dlist_entry left, const struct dlist_entry right)

static enum dentry_merge_status	dentry_right_walk_merge_check (const struct dlist_entry *e)

static enum dentry_merge_status	dentry_left_walk_merge_check (const struct dlist_entry *e)

static struct dlist_entry *	dentry_merge_to_left (struct dlist_entry left, struct dlist_entry right)

static size_t	dlist_identity (struct dlist_anchor *anchor, size_t length, const uint8_t line[length], const uint8_t ref[length], size_t begin)

static size_t	dlist_repeat (struct dlist_anchor *anchor, size_t length, const uint8_t line[length], size_t begin)

static struct dlist_anchor *	dlist_create (size_t length, const uint8_t line[length], const uint8_t ref[length])

static void	output_dlist (const struct dlist_entry *d)

static size_t	dlist_line_size_calc (const struct dlist_entry *start)

static struct dlist_anchor *	dlist_overview (size_t length, const uint8_t line[length], const uint8_t ref[length])

static struct dlist_anchor *	dlist_preview (size_t length, const uint8_t line[length], const uint8_t ref[length])

static size_t	repeating_pattern_check_ahead (size_t cnt, const uint8_t line[cnt])

static void	dlist_entry_replace (struct dlist_anchor anchor, struct dlist_entry repl)

static void	dlist_substitute_feaze (struct dlist_entry diff, const uint8_t line)

static void	dlist_list_substitute_feaze (struct dlist_entry edit, const uint8_t pattern)

static void	dlist_merge_useless_entries (struct dlist_entry *edit, int under_pressure)

Detailed Description

The encoding method is very limited in the way some kind of data reduction can be made. So, it seems, its hard to improve the algorithm. Refer test_edit*.c files for further test details.

Use this file and its content for reference. It isn't used yet.

Enumeration Type Documentation

◆ dlist_entry_type

enum dlist_entry_type

One of the possible data reduction entry, called "edit"

Enumerator
DLIST_NONE
DLIST_DIFF	This 'edit' describes a difference sequence, e.g. plain data
DLIST_REP	This 'edit' describes a repeating sequence of bytes
DLIST_EQ	This 'edit' describes an equal sequence to the previous line

◆ dentry_merge_status

enum dentry_merge_status

Enumerator
DENTRY_MERGE_REC	Merge recommended
DENTRY_MERGE_INA	Merge inappropriate, but possible
DENTRY_MERGE_IMP	Merge impossible

Function Documentation

◆ dlist_anchor_create()

static struct dlist_anchor * dlist_anchor_create ( void )

static

◆ dlist_list_clean()

static void dlist_list_clean ( struct dlist_entry * d )

static

Free memory recursive

Parameters

[in] d The 'edit' to statt to free (can be NULL to use the anchor instead)

◆ dlist_anchor_destroy()

static void dlist_anchor_destroy ( struct dlist_anchor * anchor )

static

◆ dlist_entries_count()

static unsigned dlist_entries_count ( const struct dlist_entry * d )

static

Parameters

[in] d Start of the chain (can be NULL)

Returns: Count of 'edit' entries in the chain

◆ dlist_edit_append()

static struct dlist_entry * dlist_edit_append	(	struct dlist_anchor *	anchor,
		enum dlist_entry_type	type,
		size_t	offset,
		size_t	cnt
	)

static

Append a new 'edit' to the right end of the chain

Parameters

[in,out]	anchor	The anchor of this chain
[in]	type	The type of this 'edit'
[in]	offset	Index its pattern begins in the line
[in]	cnt	Count of pattern bytes

Returns: The created (and appended) 'edit'

◆ dlist_center_find()

static struct dlist_entry * dlist_center_find	(	struct dlist_entry *	start,
		size_t	cnt
	)

static

Find the 'edit' where the center of the line is part of

Parameters

[in]	start	At which entry to start (can be NULL to use #first_entry instead)
[in]	cnt	The full line lenght of the line to calculate the middle the center

Returns: The 'edit' which covers the center of the line

◆ dentry_encoded_overflow()

static size_t dentry_encoded_overflow	(	unsigned	sat,
		size_t	value
	)

static

Calculate the overflow bytes for an 'edit'

Parameters

[in]	sat	Saturation value
[in]	value	The value to encode

Returns: Byte count to encode this overflow

Depending of the value to encode, the count of required bytes differ. This function calculates the required bytes.

◆ dentry_rel_offset_calc()

static size_t dentry_rel_offset_calc ( const struct dlist_entry * e )

static

Calculate the offset at which the previous 'edit' stops

Parameters

[in] e 'Edit' for which the write offset of its previous 'edit' is required

Returns: Relative offset from the previous 'edit'

In order to calculate the to be encoded offset of the current 'edit', the "write end" offset of the previous 'edit' is required. Every 'edit' is encoded relativ to its preceding 'edit'.

◆ dentry_encoded_size_get()

static size_t dentry_encoded_size_get ( const struct dlist_entry * e )

static

Calculate the encoded byte count for this entry

Parameters

[in] e The 'edit' in question

Returns: Size in bytes this 'edit' seizes encoded

Note: This calculation is for the 1030 encoder

◆ dentry_merge_check()

static enum dentry_merge_status dentry_merge_check	(	const struct dlist_entry *	left,
		const struct dlist_entry *	right
	)

static

Check if a merge of the given entries is helpful

Parameters

[in]	left	The left 'edit'
[in]	right	The right 'edit'

Return values

DENTRY_MERGE_REC	Merge possible, new size is smaller or at least unchanged
DENTRY_MERGE_INA	Merge inappropriate (makes no sense, enlarges the encoding, only under 'edit' pressure)
DENTRY_MERGE_IMP	Merge impossible (these two types cannot be merged)

Valid combinations:

repeat plain *******####### must be kept if the merge wouldn't be smaller

######## can be merged under 'edit' pressure

plain repeat

#******* must be kept if the merge wouldn't be smaller

######## can be merged under 'edit' pressure

equal plain *******####### must be kept if the merge wouldn't be smaller

######## can be merged under 'edit' pressure

plain equal

#******* must be kept if the merge wouldn't be smaller

######## can be merged under 'edit' pressure

repeat equal *******####### can never be merged -> if the equal part continues the repeat pattern! equal repeat

#******* can never be merged -> if the equal part continues the repeat pattern!

This routine really calculates the encoded size for a merged 'edit'. You cannot simply add the byte counts they would cover if merged, since 'offset' and 'count' overflows can add more or less bytes as well. Sometimes the encoding of the following 'edit' changes as well and could be taken into account if merging of the current 'edits' makes sense or not. But I think it's not worth the effort.

◆ dentry_right_walk_merge_check()

static enum dentry_merge_status dentry_right_walk_merge_check ( const struct dlist_entry * e )

static

Check if the given and its right neighbour can be merged

Parameters

[in] e The 'edit' to check

Return values

0	Merge possible
1	Merge inappropriate (makes no sense, enlarge encoding, only under 'edit' pressure)
2	Merge impossible

◆ dentry_left_walk_merge_check()

static enum dentry_merge_status dentry_left_walk_merge_check ( const struct dlist_entry * e )

static

Check if the given and its left neighbour can be merged

Parameters

[in] e The entry to merge

Return values

0	Merge possible
1	Merge inappropriate (makes no sense, enlarge encoding, only under 'edit' pressure)
2	Merge impossible

◆ dentry_merge_to_left()

static struct dlist_entry * dentry_merge_to_left	(	struct dlist_entry *	left,
		struct dlist_entry *	right
	)

static

Merge two 'edits' into one (right merged into left)

Parameters

[in,out]	left	The left 'edit' to be merged
[in,out]	right	The right 'edit' to merge into the left 'edit'

Returns: The left of both 'edits' with new content

The right 'edit' will be removed from the list.

Todo:: Create the dentry_merge_to_right() counterpart

◆ dlist_identity()

static size_t dlist_identity	(	struct dlist_anchor *	anchor,
		size_t	length,
		const uint8_t	line[length],
		const uint8_t	ref[length],
		size_t	begin
	)

static

Append an DLIST_EQ 'edit' to the chain

Parameters

[in,out]	anchor	The anchor of this chain
[in]	length	The length of the current line
[in]	line	Base of the current line
[in]	ref	Base of the previous line
[in]	begin	Where the pattern has begun (already two consecutive bytes are checked)

Returns: Offset, where the next pattern begins

This routine tests, if more than the already tested identical bytes follows and collects them into one DLIST_EQ entry.

◆ dlist_repeat()

static size_t dlist_repeat	(	struct dlist_anchor *	anchor,
		size_t	length,
		const uint8_t	line[length],
		size_t	begin
	)

static

Append an DLIST_REP 'edit' to the chain

Parameters

[in,out]	anchor	The anchor of this chain
[in]	length	The length of the current line
[in]	line	Base of the current line
[in]	begin	Where the pattern has begun (already two consecutive bytes are checked)

Returns: Offset, where the next pattern begins

This routine tests, if more than the already tested same bytes follows and collects them into one DLIST_REP entry.

Todo:: Refer repeating_pattern_check_ahead()

◆ dlist_create()

static struct dlist_anchor * dlist_create	(	size_t	length,
		const uint8_t	line[length],
		const uint8_t	ref[length]
	)

static

Create a list of 'edits' based on the current and previous line

Parameters

[in]	length	The length of the lines
[in]	line	Base of the current line
[in]	ref	Base of the previous line

Returns: The anchor of the created chain

Todo:: If the equality of both lines are a repeating pattern, it's maybe better to change its type into a DLIST_REP type

Das geht schief wenn: prev: …0xff 0xff 0xff 0xe0 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00 curr: …0xff 0xff 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00 ^^^^ Jetzt wird ab hier ein repeat erkannt (bis zum Zeilenende!). ^^^^ ab hier sind aber beide Zeilen leer und gleich!

◆ output_dlist()

static void output_dlist ( const struct dlist_entry * d )

static

Output the chain in a human readable list

Parameters

[in] d First 'edit' to report (can be NULL, then no report at all follows)

Note: For debugging purpose only

◆ dlist_line_size_calc()

static size_t dlist_line_size_calc ( const struct dlist_entry * start )

static

Calculate the size of the whole line if encoded

Parameters

[in] start First 'edit' to report (can be NULL, then the anchor is used instead)

Returns: Size in bytes

◆ dlist_overview()

static struct dlist_anchor * dlist_overview	(	size_t	length,
		const uint8_t	line[length],
		const uint8_t	ref[length]
	)

static

Parameters

[in] length Length in bytes of the active content

Todo:: DLIST_EQ and DLIST_REP edits can overlap

Eine andere Möglichkeit wäre, zunächst nur auf Gleichheit der Zeilen zu testen und dafür 'edit'-Einträge zu erzeugen. Dann im nachgeschalteten Test, die Räume zwischen diesen Einträgen verarbeiten und ggf. auf Ersetzen oder Wiederholen umändern. Das würde die Komplexität pro Test-Schritt rausnehmen.

Mit den verketteten Listen sollte das auch gehen, einen Eintrag durch mehrere zu ersetzen bzw. anpassen. Beispielsweise einen "diff"-Eintrag nehmen mit seinem Start und Ende und den wiederum wie eine Zeile in diff und rep aufteilen und dann anschl. die neu entstandenen edit-Einträge statt dem originalen einzuhängen. Das ginge dann mehr oder weniger rekursiv.

◆ dlist_preview()

static struct dlist_anchor * dlist_preview	(	size_t	length,
		const uint8_t	line[length],
		const uint8_t	ref[length]
	)

static

Parse the input and separate it into 'match with the previous line' and 'mismatch with the previous line'

Parameters

[in]	length	Length of line in bytes
[in]	line	The current line to examine
[in]	ref	The previos line to compare (can be NULL)

Returns: A DLIST anchor

This is the first step of three to parse the line to print into matching, non-matching and repeating pattern. Since the algorithm got more and more complex to handle all corner cases, this function is now the result to reduce the complexity again: It separates only matching and non-matching sequences (comparing to a previous line). The non-matching sequences will be processed in the next step in dlist_substitute_feaze(). If no previous line is given, matching sequences will be found by comparison with 0x00.

The regular workflow is:

separate the line into matching and non-matching pattern via dlist_preview()
separate each non-matching 'edit' from the previous step via dlist_substitute_feaze()
merge useless 'edits' via dlist_merge_useless_entries()
encode the 'edits' into the printer's wire data

◆ repeating_pattern_check_ahead()

static size_t repeating_pattern_check_ahead	(	size_t	cnt,
		const uint8_t	line[cnt]
	)

static

Check ahead how long a repeat sequence is

Parameters

[in]	cnt	Count of bytes line points to
[in]	line	The start of the repeat pattern

Returns: Lenght in bytes of the repeat sequence

Precondition: cnt must be at least '1'

◆ dlist_entry_replace()

static void dlist_entry_replace	(	struct dlist_anchor *	anchor,
		struct dlist_entry *	repl
	)

static

Replace 'edit' repl from one chain with a different chain

Parameters

[in,out]	anchor	The chain which should replace repl
[in]	repl	The entry to replace

At the end repl is part of anchor and can be removed.

Precondition: The anchor must contain at least one element.

◆ dlist_substitute_feaze()

static void dlist_substitute_feaze	(	struct dlist_entry *	diff,
		const uint8_t *	line
	)

static

Feaze a substitute edit into real substitute and repeating

Parameters

[in,out]	diff	The DIFF edit entry to feaze
[in]	line	Base of the current line starting at diff's 'edit'

Intended to work on substitute edits dlist_preview() has sorted out.

Precondition: The line's data should only contain unique data or repeating byte, e.g. dlist_preview() should have already run.

The diff edit will be replaced by the result (if any) and its memory freed.

Attention: This step is only required for encoding methods which supports 'substitute edits' and 'repeat edits'.

◆ dlist_list_substitute_feaze()

static void dlist_list_substitute_feaze	(	struct dlist_entry *	edit,
		const uint8_t *	pattern
	)

static

Encode all non-matching 'edits' in a line

Parameters

[in,out]	line	The line to encode the printer's wire data to
[in]	edit	The start 'edit' in the line (can be NULL, but should not)
[in]	pattern	Start of the pattern to write

Attention: This step is only required for encoding methods which supports 'substitute edits' and 'repeat edits'.

◆ dlist_merge_useless_entries()

static void dlist_merge_useless_entries	(	struct dlist_entry *	edit,
		int	under_pressure
	)

static

Merge useless 'edits' into its neighbours

Parameters

[in,out]	edit	The start of the chain (can be NULL)
[in]	under_pressure	Not '0' if we are under 'edit' count pressure

Sometimes useless 'edits' are created, like a DLIST_EQ with less than three byte lengths. These are not worth to keep, since the encoding of the neighbour 'edits' needs more bytes than it saves by keeping the DLIST_EQ 'edit'.

This routine walks along the whole chain and tests at each 'edit' if it can be merged with its right neighbour. If yes, the right neighbour is merged into it and removed from the chain.

Covered case:

[EQU][DIFF] -> [DIFF]
[DIFF][EQU] -> [DIFF]
[DIFF][DIFF] -> [DIFF]

If it has done a merge, it continues to check the new right neighbour of the merged 'edit'.

Note: A merge - if possible but inappropriate - will however be done if under_pressure signals (e.g. not '0') we need to reduce the 'edit' count.

Data Structures

Enumerations

Functions

Detailed Description

Enumeration Type Documentation

◆ dlist_entry_type

◆ dentry_merge_status

Function Documentation

◆ dlist_anchor_create()

◆ dlist_list_clean()

◆ dlist_anchor_destroy()

◆ dlist_entries_count()

◆ dlist_edit_append()

◆ dlist_center_find()

◆ dentry_encoded_overflow()

◆ dentry_rel_offset_calc()

◆ dentry_encoded_size_get()

◆ dentry_merge_check()

######## can be merged under 'edit' pressure

#******* must be kept if the merge wouldn't be smaller

######## can be merged under 'edit' pressure

######## can be merged under 'edit' pressure

#******* must be kept if the merge wouldn't be smaller

######## can be merged under 'edit' pressure

#******* can never be merged -> if the equal part continues the repeat pattern!

◆ dentry_right_walk_merge_check()

◆ dentry_left_walk_merge_check()

◆ dentry_merge_to_left()

◆ dlist_identity()

◆ dlist_repeat()

◆ dlist_create()

◆ output_dlist()

◆ dlist_line_size_calc()

◆ dlist_overview()

◆ dlist_preview()

◆ repeating_pattern_check_ahead()

◆ dlist_entry_replace()

◆ dlist_substitute_feaze()

◆ dlist_list_substitute_feaze()

◆ dlist_merge_useless_entries()