# CRSCE

Cross-Sums Compression and Expression (CRSCE) is a lossless data compression algorithm with a predictable compression rate. The algorithm was developed by Sam Caldwell. The first experimental concept was developed in 1993 in Austin, Texas. The first viable implementation was developed in 2024. Due to computational complexity, CRSCE was only made feasible by recent development of affordable GPU technologies. The algorithm and its software has been published under an MIT License.

# Abstract

The Cross Sums Compression and Expansion (CRSCE) algorithm is a novel, lossless compression technique designed to process arbitrary data inputs with predictable efficiency and guaranteed integrity. The algorithm represents input data as a two-dimensional binary matrix ($CSM[sxs]$) from which it computes four (4) one-dimensional cross-sum matrices. These are the "Lateral Sum Matrix" ($LSM[s]$), "Vertical Sum Matrix" ($VSM[s]$), "Diagonal Sum Matrix" ($DSM[s]$), and "Anti-Diagonal Sum Matrix" ($XSM[s]$). These cross sums matrices condense structural properties of the input data. Additionally, CRSCE employs a cryptographic hash chain ($LH[s]$) to ensure data integrity and prevent collisions. Using a fixed block size of $s=512$, CRSCE achieves a consistent compression rate ($C_{r}$) of $42.97\%$, outperforming many traditional algorithms in efficiency. While larger datasets yield higher compression rates, the computational cost of both compression and decompression increases proportionally. To balance this trade-off, larger datasets are compressed as independent blocks. However, CRSCE’s reliance on cryptographic hashing makes it unsuitable for real-time compression, and its requirement to load the entire compressed block into memory limits real-time decompression to an entire block. This paper introduces the CRSCE algorithm, evaluates its performance across various block sizes, and explores its potential applications and limitations in contexts demanding lossless compression and data integrity.

# Introduction
## Background

Data compression is a cornerstone of modern computing, reducing the storage and transmission costs associated with increasingly large datasets. While lossy compression techniques, such as JPEG for images and MP3 for audio, dominate multimedia applications, lossless compression remains essential for scenarios requiring exact reconstruction of the original data. These include archival storage, cryptographic systems, and scientific data, where even minor deviations can lead to significant errors.
General-purpose lossless compression algorithms, such as LZ77, Huffman coding, and DEFLATE, are widely used across industries. However, these algorithms often struggle to achieve efficient compression on highly random or binary datasets, as they rely on dictionary-based redundancy elimination or entropy-based statistical modeling. For such data, compression rates are unpredictable and often suboptimal, making it difficult to assess performance without fully processing the input dataset.
The Cross Sums Compression and Expansion (CRSCE) algorithm offers a novel solution to these challenges by leveraging a mathematically rigorous approach. Instead of relying on sequence-based redundancy, CRSCE represents input data as a binary matrix and computes structural summaries using cross-sum metrics. By incorporating a cryptographic hash chain, CRSCE also ensures data integrity and prevents collisions, making it suitable for applications requiring both compression and verifiability.
A key advantage of CRSCE is its predictable compression rates. Unlike traditional algorithms, CRSCE's compression efficiency is primarily determined by the block size (s), rather than the content of the message. For a fixed block size of $s=512$, CRSCE achieves a consistent compression rate ($C_{r}$) of $42.97\%$, regardless of the entropy or structure of the input data. Larger block sizes yield even higher compression rates but at the cost of increased computational complexity. This paper introduces the CRSCE algorithm, detailing its methodology, performance characteristics, and practical applications. We demonstrate how CRSCE balances compression efficiency and scalability while addressing its limitations, particularly in real-time processing scenarios.

## Problem Statement

Traditional lossless compression algorithms, such as LZ77, Huffman coding, and DEFLATE, achieve limited efficiency for certain data types, particularly high-entropy or binary data. These algorithms rely heavily on dictionary-based redundancy elimination or entropy coding, which are effective only when the input data exhibits predictable patterns or repeatable structures. In the absence of such structure, these methods often fail to achieve meaningful compression.
Furthermore, existing lossless algorithms do not provide cryptographic guarantees of data integrity, which are increasingly critical in applications such as archival storage, distributed systems, and cryptographic environments. Ensuring that compressed data remains unaltered during storage or transmission typically requires additional layers of verification, increasing computational overhead and complicating implementation. The Cross Sums Compression and Expansion (CRSCE) algorithm addresses these limitations by combining modular arithmetic, which captures the structural properties of binary matrices, with cryptographic hashing, which prevents collisions and ensures data integrity. CRSCE’s unique design achieves predictable and consistent compression rates based on block size, regardless of input data entropy.
However, this approach comes with trade-offs. While CRSCE achieves high compression efficiency for sufficiently large datasets, the computational complexity of its reconstruction process increases significantly with matrix size (s). This makes CRSCE ideal for applications where storage efficiency and data integrity are prioritized over real-time performance, such as archival systems or secure data transmission.

## Objective and Contributions

This paper introduces the Cross Sums Compression and Expansion (CRSCE) algorithm as a novel, lossless compression technique that addresses key limitations in traditional approaches. CRSCE achieves predictable compression rates, ensures data integrity, and scales efficiently for large datasets. The primary contributions of this work are as follows:
* Leverages Cross-Sum Metrics ($LSM$, $VSM$, $DSM$, $XSM$): CRSCE captures the structural properties of binary matrices through modular arithmetic, enabling efficient compression of arbitrary data inputs.
* Ensures Data Integrity with $LH$: A cryptographic hash chain prevents collisions and guarantees exact reconstruction, making CRSCE suitable for applications requiring verifiable data compression.
* Scales to Large Datasets: By fixing the block size at $s=512$, CRSCE balances compression rate ($C_{r}$) and computational complexity, achieving a consistent compression rate of $42.97\%$. Larger block sizes yield higher compression rates while maintaining scalability.
We evaluate CRSCE’s performance across various block sizes, highlighting $s=512$ as the crossover point where the algorithm begins to outperform traditional compression methods. Additionally, potential applications in archival storage, distributed systems, and cryptographic environments are discussed.

# Methodology: Compression
## Algorithm Design

The Cross Sums Compression and Expansion (CRSCE) algorithm is a lossless compression technique designed to operate on structured binary data. The input data is represented as one or more blocks. Each block is a two-dimensional fixed-size matrix known as $CSM$. The size of CSM is $sxs$, where $s=512$, the currently optimal matrix size balancing performance and compression rates. Input sizes greater than $32KB$ must, therefore, be processed as separate $CSM$ blocks.
The algorithm leverages two primary mechanisms:
* Cross-sum metrics, which encode the structural properties of the binary matrix.
* Cryptographic hash chains, which prevent collisions and ensure data integrity.

## Initial Data Load

Assuming $s=512$ ($32KB$) blocks, CRSCE reads the data source $32KB$ at a time to populate a two-dimensional matrix called $CSM$, where—
$CSM={\begin{bmatrix}a_{0,0}&a_{0,1}&,...,&a_{0,s-1}\\a_{1,0}&a_{1,1}&,...,&a_{1,s-1}\\.&,...&,...,&,...\\a_{s-1,0}&a_{s-1,2}&,...,&a_{s-1,s-1}\end{bmatrix}}$
and $a={0,1}$. This can be optimized in an implementation for execution speed, but in theory, all raw inputs are represented in the $CSM$ matrix when loaded. From this $CSM$ matrix, we can compress the input by calculating the cross-sums and integrity-verifying hashes.

## Cross-Sum Matrices

For every bit ($CSM_{r,c}$) read, we calculate four (4) cross-sum matrices to summarize the structural properties of the binary matrix:
* Lateral Sum Matrix ($LSM$): The sum of all elements in each row: $LSM_{r}=\sum _{c=0}^{s-1}CSM_{r,c}$, where $r$ represents the row index and $c$ represents the column index.
* Vertical Sum Matrix ($VSM$): The sum of all elements in each column: $VSM_{c}=\sum _{r=0}^{s-1}CSM_{r,c}$
* Diagonal Sum Matrix ($DSM$): The sum of elements along cyclic diagonals:$DSM_{i}=\sum _{r=0}^{s-1}CSM_{r,(r+i)\ mod\ s}$, where i denotes the diagonal offset.
* Anti-Diagonal Sum Matrix ($XSM$): The sum of elements along cyclic anti-diagonals:$XSM_{i}=\sum _{r=0}^{s-1}CSM_{r,(s-r+i-1)\ mod\ s}$
These metrics condense the matrix’s structural properties into a compact representation, reducing redundancy while preserving critical information.

## Cryptographic Integrity

To ensure data integrity and prevent collisions, CRSCE incorporates a cryptographic hash chain (LH). The hash chain is calculated row by row, starting with an initial nonce:
$N=Sha256(nonce)$
where the nonce must be the same for all systems operating on a given compressed signal such that during decompressing systems can also calculate the hash chain from a common nonce to verify the decompressed signal.
For each row of CSM[r,c], LH[r] is computed as— ${\begin{aligned}&LH_{0}=Sha256(Concat(N,CSM_{0,0},CSM_{0,1},\dots ,CSM_{0,s-1}))\\&LH_{1}=Sha256(Concat(LHASH_{0},CSM_{1,0},CSM_{1,1},\dots ,CSM_{1,s-1}))\\&LH_{2}=Sha256(Concat(LHASH_{1},CSM_{2,0},CSM_{2,1},\dots ,CSM_{2,s-1}))\\&...\\&LH_{s-1}=Sha256(Concat(LHASH_{s-2},CSM_{s-1,0},CSM_{s-1,1},\dots ,CSM_{s-1,s-1}))\end{aligned}}$
Which can be summarized as—
$LH_{r}=Sha256(Concat(LH_{r-1},CSM_{r,0},CSM_{r,1},...,CSM_{r,s-1}))$
where-- $r=\left\{1,...,s-1\right\}$.

## Output Encoding

For a given $CSM$ block, the compressed output is encoded as a packed bit stream, which can be represented as—
$Output=Concat(LH_{0},...,LH_{s-1},LSM_{0},...,LSM_{s-1},VSM_{0},...,VSM_{s-1},DSM_{0},...,DSM_{s-1},XSM_{0},...,XSM_{s-1})$
The order of serializing the component outputs is important, as the size of the Lateral Hash matrix ($LH$) is always a byte-aligned multiple of 256 bits, and thus quicker to deserialize and free its memory. But the cross-sum matrices are not byte-aligned since for $s=512$, only nine (9) bits are required to represent the final cross sum, calculated as—
${\begin{aligned}&b=log_{2}(s)\\&b=log_{2}(512)=9\end{aligned}}$
This means that when the cross-sums are calculated, an integer of at least 16 bits will be required but the final output must be packed to their 9-bit representation for the final output. Likewise, when decompressing a signal, the cross sums must be parsed on their b-bit boundary.

## Scalability
### Data Partitioning

For larger input signals larger than $32KB$, CRSCE breaks the signal down into consistent $32KB$ blocks, which are compressed and stored as independent blocks. These blocks provide the first opportunity for parallel processing of the input during both compression and decompression. It is possible that larger inputs can be mapped to different processes or even different machines to improve compression speeds with the final result reduced to a single output stream.

### Cross-Sum and Hash Calculations

During compression, additional speed can be realized by mapping each row, column and diagonal in $CSM$ to a different asynchronous process to calculate the corresponding cross-sum. Likewise, rows can be hashed to create $LH_{r}$ quickly by mapping each row to a different process or thread. Assuming $CSM$ is loaded into memory as a contiguous block, the different perspectives of each cross-sum or hash matrix can operate on this matrix independently without conflict as the $CSM$ matrix does not change during the process.

### Output Encoding

Output encoding also has potential for parallel processing. Assume that the output memory is allocated as a single structure first. References to this structure can then be passed to asynchronous bit-packing threads which can then handle serialization of the $LH$ hash matrix as well as each cross-sum, reducing the time required to perform the 9-bit packing process.

## Performance
### Expected Compression Rates

The compression rates of CRSCE are predictable as a function of block size ($s$), where $s$ is the length and width of a $CSM$ matrix and the number of elements in each cross sum or hash matrices. The algorithm defines $s$ as—
$\left\{\,s\in \mathbb {Z} \;{\bigg |}\;{\begin{aligned}&s>292,\\&s^{2}\equiv 0{\pmod {b}},\\&b=\log _{2}(s)\end{aligned}}\,\right\}$
From this, the compression rate (Cr) can be calculated as—
$C_{r}=1-{\frac {4sb+256s}{s^{2}}}$
which can be simplified to—
$C_{r}=1-{\frac {4b+256}{s}}$
Where the numerator represents the compressed output signal length and the denominator represents the raw (uncompressed) input signal. Calculating the compression rates ($C_{r}$) for all values of $s$, we see that—
CRSCE Compression Rates By Block Size :
| Block Size (s) | b | Total Data Size ($s^{2}$) | Compression Rate ($C_{r}$) |
| 256 | 8 | $256^{2}=8KB$ | -14.5% |
| 512 | 9 | $512^{2}=32KB$ | 42.97% |
| 1024 | 10 | $1024^{2}=128KB$ | 73.12% |
| 2048 | 11 | $2048^{2}=512KB$ | 90.54% |
No matter the content of the input, CRSCE will return an output with the same expected size. This is a novel feature of CRSCE. While compression rates increase as the size of $CSM$ increases, so too does the complexity and memory requirements to both compress and decompress a signal. Setting the value of $s$ to $512$ (the lowest viable $CSM$ size) guarantees a $42.97\%$compression for all inputs, outperforming traditional algorithms on average and minimizing the processing overhead.

### Processing Speeds

This paper does not consider processing speeds, as these are implementation specific. However, assuming no parallelization, the algorithm is faster to compress than to decompress signals. This is due to the nature of decompression, discussed later.

# Methodology: Decompression
## Deserialization And Loading

To decompress data, the algorithm must load all of the cross sums and hashes into memory. This requires parsing the file into its one or many blocks. For each block, the algorithm must then unpack the blocks into their $b$-bit wide sums such that all cross sums and the lateral hashes are in memory. Integrity can be checked quickly by ensuring that the sum of the unpacked cross sum matrices are all the same, as follows:
$T=\sum _{k=0}^{s-1}LSM_{k}=\sum _{k=0}^{s-1}VSM_{k}=\sum _{k=0}^{s-1}DSM_{k}=\sum _{k=0}^{s-1}XSM_{k}$
Since each block is an independent problem, the decompression process described in this section must be applied to each block. For efficiency this can be done in parallel where memory resources allow, to solve many blocks simultaneously.

## Iterative Decompression

The general process of decompression is repeated until the block is solved, starting with the Elimination Phase, Radditz Sieve Phase, Sift Phase and Verification Phase. As elements of the $CSM$ matrix are solved, they are locked such that other elements can be iteratively adjusted. When all rows of the $CSM$ matrix pass the verification phase, the process ends and the resulting $CSM$ matrix can be serialized and written to the output device as a solution.

## Elimination Phase

The first phase of the decompression process, which must be performed for each iteration is the elimination phase. This phase increases decompression speed by solving the obvious solutions in the remaining CSM matrix by applying one or more of the rules described in this subsection. With each iteration of the decompression process, the likelihood that the elimination phase will solve a set of elements should increase as the number of unsolved $CSM$ elements decreases.
The first two rules of the elimination state that where a cross sum equals the s-value for a block (represented by the $CSM$ matrix), all corresponding $CSM$ values must be set to one ($1$). Likewise, where a sum equals zero ($0$), the corresponding elements can be set to zero ($0$). Thus, if $LSM_{r}$ equals zero ($0$) or one ($1$), the elimination phase can set $CSM_{r,0,...,s-1}$ to zero ($0$) or one ($1$), respectively. Likewise, the same can be said for any column, diagonal or anti-diagonal.
The third rule of the elimination phase is applied only on the first iteration of the decompression process, where elimination can compare the lateral hash ($LH$) array elements to the known $SHA256$ hashes for the $s$-bit alternating pattern $0101$ and $1010$ and where the hashes match, the elimination phase can immediately solve the corresponding row using the matching pattern.
As the elimination pattern solves elements of the $CSM$ matrix, the elements are locked to prevent further changes by subsequent decompression phases. The values of the solved elements are deducted from the cross sums, and the remaining bits for which a solution is needed will be represented in the resulting cross sum values.
If at the end of the elimination phase, there are no unsolved $CSM$ elements, (e.g. all cross sum values are zero ($0$), then the process terminates and the Verification phase (discussed later) is invoked. Otherwise the algorithm proceeds to the Radditz Sieve.

## Radditz Sieve Phase

Following the elimination phase, the algorithm must distribute the bits remaining in the four cross sums to the open spaces of the $CSM$ matrix. The process cannot simply distribute these values left-to-right, top-to-bottom or in any similar linear pattern as this creates a biased proposed solution which results in additional work to sift the result to the actual solution. Instead, the Radditz Sieve process randomly selects a $CSM_{r,c}$ element then calculates the probability $pCSM$ using a noisy-OR computation—
$pCSM_{r,c}=1-\left({\frac {LSM_{r}}{s}}x{\frac {VSM_{c}}{s}}x{\frac {DSM_{r,(r+i)mods}}{s}}x{\frac {XSM_{r,(s-r+i-1)mods}}{s}}\right)$
and the overall probability ($T$) as—
$LSM_{r}={\frac {\sum _{k=0}^{s-1}LSM_{k}}{s}}$
If $pCSM>=T$ then $CSM_{r,c}=1$, otherwise the value is zero ($0$). Where the sieve process hypothesizes the $CSM$ element is one ($1$), the cross sum is decremented.
The random selection of $CSM$ elements and the hypothetical solution is developed until either all cross sums are zero ($0$) or until no cross sum values can be allocated (e.g. if $LSM_{r}=0$ and $VSM_{c}>0$, then $CSM_{r,c}$ cannot be solved for $CSM_{r,c}$. Once either of these end states are reached, the Radditz Sieve is terminated and the next phase begins.

## Sift Process

Following the Radditz Sieve process, a verification cycle is performed to check and verify if any rows have been solved. This process, discussed later, compares the hashes of $CSM$ that match the lateral hash matrix ($LH$). Where any hash matches, the corresponding elements of the $CSM$ row are locked to prevent further change and the row is considered “solved.” After this verification step, the algorithm starts at the row with the fewest unsolved $CSM$ elements and begins to “sift” the bits, testing unsolved possibilities in a near brute force manner. This can be distributed across many asynchronous cores to increase the speed of the operation. But for each attempt, hash validation indicates whether the row is solved. When a given row is solved, the Sift phase terminates, and the next iteration begins with another round of the elimination phase (discussed earlier).

## Verification Phase

During termination, the algorithm iterates over each $CSM$ row, calculates its $SHA256$ hash and compares it to the corresponding lateral hash ($LH$) matrix element. If all hashes are equal, the $CSM$ is solved and the block can be written to output before the process is terminated.
If the two hashes are not equal, the row is marked as unsolved, its unlocked values are cleared, and its cross sums are reverted appropriately. However, for each $LH$ hash that matches, the entire corresponding row is marked as locked to prevent further change. The process then launches a new iteration of the elimination-sieve-sift process (discussed earlier).

## Scalability

The decompression process has limited scalability due to the complexity of its processes. However, there are some opportunities to distribute the decompression problem across multiple independent systems at the block level. An implementation could map many blocks to several asynchronous processes or devices then aggregate the resulting decompressed block data to create a final artifact. This may increase the ability to scale the algorithm to larger data sets.
One limit intentionally placed on scalability is the size of the block. The $CSM$ size value ($s$) is intentionally limited to $512$ bits ($32KB$), the smallest $s$-value possible, to reduce the decompression time and complexity. As systems become more powerful and as GPU prices fall and these devices become more ubiquitous, the algorithm may be able to take advantage of the highly parallel nature of GPUs to improve performance and thereby allow the value of $s$ to be increased. With an increase in the $s$-value will come an exponential increase in complexity and an increase in decompression time. But this will be offset by an increase in compression rates.
The sky is not the limit, however. At some unknown value of $s$, the risk of collisions becomes real. While Sha-2 may be substituted for Sha-3 when calculating $LH$to address some of the collision concerns at these higher values of $S$, this will likely do little more than shift the collision risk to a higher $s$-value. It will not eliminate the same.

## Performance

Performance of the decompression process degrades as the value of s increases. In fact, compared to other conventional compression algorithms, CRSCE’s performance is horribly slow. Its trade off is its guaranteed compression rates, which may justify some of its performance cost in some use cases. However, absent highly parallel processing systems, the performance of CRSCE will not be improved.
There is the argument against CRSCE that the algorithm is nothing more than an informed brute force attack on the lateral hashes. To some extent this argument has weight. The algorithm does appear at first to be a form of brute force when decompression reaches the sift phase. It is made less “brute force” when one considers the helpful hints at the solution provided by the elimination phase and Radditz Sieve. Further work, of course, is needed to reduce the time spent in the sift phase and to find more efficient methods to take the output of the elimination-sieve and realize the complete solution.

# Conclusions

CRSCE is a promising new direction in data compression with extraordinary potential. For data retention and archival, the value of CRSCE is obvious since compression is fast and predictable and decompression is less likely and often would have the expectation of an increased delivery time frame. Further, the cost of decompression under the CRSCE algorithm is almost certainly to be reduced over time as quantum computing and other technologies emerge to reduce decompression time. This algorithm has been a work in progress since 1993, and over the past three decades, the author has made many improvements, solicited feedback from peers and iteratively arrived at the conclusion that the current 2024 version of the algorithm is viable and ready for consideration by the wider technology community.