Anonymous wrote at 2007-08-29 03:14:

Hello. Actually 2^32-5 is a prime. It os possible to implement multiply modulo 2^32-5 using only shifts. This quite fast to do. My suggestion is to encode blocks containing only values in the range [0..2^32-7], Use a special value 2^32-6 to indicate that the value is out of range(in the six remaining values ). Finally store other possible 6 values in a separate storage. Statistically this separate storage will only require about 1 byte for every 3 gygabytes which will be negligible. This was just an idea that can be further improved.

Zbr wrote at 2007-08-30 15:19:

Such set of basis operations in 2^3-5 will not be able to catch all possible words. So, it will be forbidden to have a full 32 bit words on the storage, since every word is being used to calculate appropriate checksum, which is unacceptable.

Anonymous wrote at 2007-08-30 16:48:

Hello. Only 5 possible values out od 2^32 will be missing. The possibility that i suggested is to store use an escape value to mean a value is among the six missing value. This value could be stored elsewhere. Alternatively one could encode with each block 2 bytes indicating a range of 5 values that don't appear in a block. 2 bytes will be sufficient for blocks of size 32 Kbytes which will make space overhead negligible. The range associated with each block will permit to reduce range of values to encode to 2^32-5.

Zbr wrote at 2007-08-30 17:00:

No, _each_ word, which has its high bits out of 32 set (2^32-5) must be stored everywhere. Since each word is being used to produce a checksum, words, which are larger than 2^32-5 (not its position, but actual value stored on the disk), will not participate and thus must be either stored elsewhere or special math be added to handle them.

Anonymous wrote at 2007-08-30 19:15:

Hello. Suppose you have an array 8192 words of length 32 its each(which gives a block size of 32 Kbytes). You have only at most 8192 different values. So if you take the range [0..65536-1], You are sure that you can find a sub-interval of length 8 in that range that never appears in the block. In fact we need only intervals of length 5. So we can use 2 bytes to indicate the beginning of that interval of five 5 values that never appear. Let this value be noted x. Then you can each value y in the block by operation y'=y-x. Now you will obtain that all values will be in the range [0..2^32-6]. Determining the small empty range of length 5 is simple to do by traversing the whome block and using a bitmap of 655536 values. The only problem is to store the small 2 bytes value somewhere. Space overhead will of course be very small: only 2 bytes per block of 32Kbytes.

Zbr wrote at 2007-08-30 19:39:

Hi. This will not work, if the whole storage (say 2^64 bytes) contains of 0xff bytes only, and we use 32 bit words. All that values must be stored outside that part of the distributed storage, which is processed in our field with described above operations. You can not split the word. If you want to split the word into part which is in the 2^32-5 range and part which is out of the above boundary, then you still need to store 3 bits for _each_ word somewhere. And perform some math on that bits. And need to have some knowledge on how to search those 'lost' 3 bits for any given word.

This is all about to move to bigger words, while your approach requires to add additional at least two operations (binary OR and shift for the higher 3 bits) for each word, not counting additional lookups and data reading.

Anonymous wrote at 2007-08-30 19:59:

Hello. My idea is to detect in each block of 32Kbytes a range of 5 values in [0..2^16-1] that never appear. Obviously such range exists, because wa have at most 8192 different values in a block of 8192*32bits(In fact there exists a range of 8=655536/8192 consecutive values that never appear in a set of 8192 values). Let x be the first value of the range. We can store x using only 2 bytes. Now we can transform all of the 8192 values using the transformation y'=y-x. This will give us an array of 8192 values all in range [0..2^32-6].

Zbr wrote at 2007-08-30 20:30:

Yes, but we still need to store somewhere those additional 5 values. And perform additional operations when they are decoded and encoded. And additional storage for those 5 values per 32kb must be processed too (calculate checksum and store it somewhere). The only need for having 32 bit word is to perform fast checksum calculation (roughly 3 times faster according to my checks at http://tservice.net.ru/~s0mbre/blog/devel/math/codes/2007_06_19.html ) over 32 bit values instead of 4 operations of 8 bits. Galois field operations can possibly be faster in such field, but added complexity to handle 'lost bits' and number of bugs really not worth the idea.

Anonymous wrote at 2007-08-30 21:40:

Hello. Actually i have found a simpler and faster way that will use 4 bytes of overhead per block. We generate a random value in the range [0..2^32-1]. Let this value be called x. We traverse the whole block and transform each value y'=y-x. During the scan, we check if some value y' is in the range [2^32-6..2^32-1]. If this is the case we stop scanning and regenerate a new random value x and redo operation. if that fails we regenerate a new random value etc... Unti we obtain a good result(no y' values is in range [2^32-6..2^32-1]). For blocks of 4096 bytes the first iteration will fail with very small probability of less than (1/10^6). So the algorithm will unlikely go beyond first iteration. I don't think that my suggestion will give a noticeable slowdown.

Zbr wrote at 2007-08-30 22:03:

Consider the case, when you have incremental 32 bit counter stored in the block. In such case you will scan the whole block until you finally find a value which is in [2^32-6..2^32-1] range (module previous decrements). All your approaches described above have the only aim to split the whole storage into two parts, one of which contains data words, which values are below some limit, and another one with the rest of the data. With some probability the latter case will be small enough, but there is possibility, that storage will not obey to your demands and thus the whole idea will result in the very wrong behavior. Splitting words in unacceptable.

Anonymous wrote at 2007-08-30 22:32:

Hello. No the goal of my suggestion is to find a reversible transformation from n words to n+2 or n+4 words. No additional storage is needed beyond n+2 or n+4 words. The two or four bytes will describes a values x such that no values in original block is in [x..x+4]. As there is at most n different values in a blocks and n<<2^32 we will find such a value x with very high probability. Now we will recode each value y in the block into value y'=y-x. Now obviously every y' will be in interval [0..2^32-6]. My suggestion in previous post was to generate a random x. Then do transformation. If transofrmation fails we simply try another x, and so on until we succeed. In fact the suggestion of storing values outside range was my first one. the suggestion in last 4 posts is different and requires only 2 or 4 bytes by block and doesn't need any space beyond that.

Zbr wrote at 2007-08-30 22:37:

What will happen, when newly written data is outside your previous interval? It will require the whole storage rebuild. And even more, if you transform every word to be y1 = y0 - x, then values, which were less than x, now will have high bits set and thus again not be able to work with given modulo operations.

Anonymous wrote at 2007-08-30 23:17:

I thought that x is stored per block and not for whole storage. So only a single block is rebuilt at any time. Now i don't understand second problem you are mentioning. Given suitable value of x all values in a block will be in [0..2^32-6]. Your argument is only valid if interval was [0..2^29-1] but interval is [0..2^32-6]. Now doing multiplication in field of [0..2^32-6] can easily be done using multiplication that extends to 64 bits(Whis is standard multiplication in current processors). Then doing 3 shifts we can do division by 2^32-5 of 64 bits result of multiplication . This is quite simple: we take higher 32bits word, left shift it by 5 positions, then adding it(with 64 bits addition) to low 32bits word with result stored in 64 bits. Doing the same a second time(left shift by 5 positions high word then adding it to low word), you will obtain a value in range [0..2^32-1]. Finally we check if the result is above 2^32-5. If it is the case we subtsract 2^32-5 from it(this is very unlikely to induce a branch mis-prediction). Now if you compare this to multiplication over galois field of 2^16. There you will need two lookup tables: one for log and one for antilog. The two lookup tables will require 256Kbytes which will not fit in L1 cache. A multiply requires three lookups. As L1 cache misses costs 15-20 cycles, we will habe a total of 45-60 cycles for a single multiply.

Anonymous wrote at 2007-08-30 23:42:

Hello. Sorry i was wrong: i should have written multiply by 5 instead of left shift by 5. So the operation of multiplication modulo 2^32-5 will require one true 32*32 bits into 64 bits mulitplication and two 64bits multiply by 5. The latter is usually implemented with one shift by 2 and an addition. I think that this is still faster than a GF[2^16] multiply.

anonymous wrote at 2007-08-31 01:11:

Hello. To clarify more about modulo 2^32-5 operation for 64 bits words. First we know that 2^32 mod (2^32-5)= 5. So we have (y*2^32+x) mod (2^32-5)=(y*5+x) mod (2^32-5). Know it might be that y*5+x is still too large(it is still a 64bits number). We decompose it into its two 32bits wordss y' and x'. Hence we will have (y*5+x) mod (2^32-5)=(y'*2^32+x') mod (2^32-5)= (y'*5+x') mod (2^32-5). The computed 64bits value y'+5*x' will be at most 2^32+30(because y' is at most 6). We finally substract 2^32-5 from that value if it is larger than 2^32-5(which will happen very rarely ).

Zbr wrote at 2007-08-31 20:19:

You seems to not understand the intention - operations in GF(16) is very fast, but I want GF(32) or GF(64), which requires to solve system of equations, since O(2^32) memory overhead is too big.

According to your idea of moving word multiplication to modulo 2^32-5 - you want to decrement every word in block, so that it will be less than 2^32-5. But if word was zero, and you will decrement it further (i.e. y1 = 0 - x in you notation above), then it can become more than 2^32-5, and thus will not be allowed to work with 2^32-5 arithmetic.

So, it is unacceptable. Actually you can implement it and show results on the random big array of data, so that there would be no misunderstanding.

Anonymous wrote at 2007-08-31 21:36:

Hello. Sorry for wasting your time, only now i understand my error. I have made a mistake and it is only now that i have realized. In fact the right tranformation is y'=y-x-5. That will give correct result and will ensure that no value y' is in interval [2^32-5..2^32-1]. This can easily be checked to work.

Zbr wrote at 2007-08-31 21:42:

It still does not work: 1 - 5 will not be in [0:2^32-5] range and thus will not be able to work with math modulo 2^32-5. To work with such limited space you need to move all words which are not in range into new device, change its range and perform crc checks on both devices.

Anonymous wrote at 2007-08-31 22:12:

Hello. My method is as follows: generate a random x. do transformation with that value of x(tranformation is y'=y-x-5 for each y). This tranformation will fail if and only if some y was in interval [x:x+4] which will make y' in intervak [2^32-5:2^32-1]. If this is the case, we can repeat with a new randomly generated values of x until we succeed. But for small blocks first attempt will fail with probability less than 1/(1million). Now if in initial block you had some value in interval [1:5], that's simple this will not work if x is in interval [0:5] but x is randomly generated. If we have generated x that doesn't work, we will try with another x. My transformation is y'=y-x-5 and not y'=y-5.

Anonymous wrote at 2007-08-31 22:38:

Hello. I have finally found the original website were i found the idea a few months ago: http://www.lshift.net/blog/2006/11/29/gf232-5.

Zbr wrote at 2007-09-01 19:04:

Thanks for the link. Idea looks just like you described number of posts above - to split all data into two parts, one of which is inside finite field in question and another one - outside with various (promising to be fast) algorithms.

I can not judge if idea is worthless or not, it should be implemented for testing. It looks interesting, but requires implementation (as far as I understood,authors yet did not completed whole project, only initial part).