In article <(E-Mail Removed)>, Michael Foukarakis <(E-Mail Removed)> writes:

> On Feb 22, 11:56=A0am, Branimir Maksimovic <(E-Mail Removed)> wrote:

>> given

>>

>> const uint64_t maxDateValue =3D 6074000998ull;

>>

>> write decode/encode date range functions

>>

>> uint64_t encodeDate(uint64_t start, uint64_t stop);

>> void decodeDate(uint64_t blob, uint64_t* start, uint64_t* stop);

>>

>> Interesting exercise

>

> Where's the exercise? In trying to figure out what the exercise is?
I guess the exercise is:

The following inequalities hold for the "start" and "stop" params of

encodeDate():

0 <= start <= stop <= 6074000998

Compress the (start, stop) pair into a single uint64_t value, so that

decodeDate() can reproduce the individual components later.

--o--

6074000998 is 1,01101010,00001001,11100110,01100110 in binary. It

contains around 32.5 bits of information. If we wanted to store two such

*unrelated* numbers, we couldn't do that. However, we can throw away one

bit of information, because we can restore the ordering (a yes/no

decision for two numbers) without transmitting it explicitly.

Thus 32.5 + 31.5 = 64.

--o--

Let base B be decimal 3,037,000,499. The greatest base-B number

representable as an uint64_t is

2 | 3 | 2,746,052,116

(digits written in decimal).

Both start and stop are not greater than "2 | 0" in base B -- see

maxDateValue.

start = t | u (base B)

stop = v | w (base B)

The value sent over the wire will look this way in base-B:

case | w | u

Cases:

stop start w < u implies this case

v|w t|u

2|0 2|0 2

2|0 1|u * 2

2|0 0|u * 1

1|w 1|u 1

1|w 0|u * 0

0|w 0|u 0

Notice that where "w < u" does NOT hold, there the case digit equals

both t and v. Also notice that where the case digit is 2, there "w" is

0, thus "case | w | u" (base-B) will not exceed the limit described

above.

Implementation:

static const uint64_t base = UINT64_C(3037000499);

uint64_t

encodeDate(uint64_t start, uint64_t stop)

{

uint64_t

t = start / base,

u = start % base,

v = stop / base,

w = stop % base;

return

w < u

? (

2u == v

? base * base * (t + 1u) + u /* t+1 | 0 | u */

: w * base + u /* 0 | w | u */

)

: base * base * t /* t | w | u */

+ base * w

+ u;

}

void

decodeDate(uint64_t blob, uint64_t* start, uint64_t* stop)

{

uint64_t case = blob / (base * base);

/* Initialize final values with low base-B digits. */

*stop = blob / base % base; /* w */

*start = blob % base; /* u */

/* Set high base-B digit. */

if (*stop < *start) {

switch (case) {

case 2:

*start += base;

case 1:

*stop += base;

case 0:

*stop += base;

}

}

else {

*start += case * base;

*stop += case * base;

}

}

Cheers,

lacos