[ntp:questions] Re: Jonathan Buzzard's radioclkd and FreeBSD

Terje Mathisen terje.mathisen at hda.hydro.com
Wed Nov 19 07:47:03 UTC 2003


Dave Thompson wrote:

> On Mon, 10 Nov 2003 13:23:54 +0100, Terje Mathisen
> <terje.mathisen at hda.hydro.com> wrote:
> 
> <snip>
> 
>>/* These operations are valid for any date after 1600-03-01,
>>    according to the modern calendar
>>*/
> 
> 
> But only up to mid-1779 if unsigned int is only 16 bits, as is
> permitted. Simplest to just use unsigned long, which is at least 32

As I specified later on, my algorithm depends upon having at least 
29-bit ints, so that is OK. OTOH, I do agree that using some other 
typedef might be better.

> bits, but may be more (e.g. I32L64); or in C99 use [u]int_least32_t
> from <stdint.h> but that isn't very widespread yet although <stdint.h>
> can be easily patched onto a C90 implementation; or make it adjust
> automatically (using preprocessor, autoconf, or the like), but bearing
> in mind that if this function is exported/published, the declared
> return type seen by callers must agree with the definition (body).
> 
> 
>>#define MASKSHIFT (8 * sizeof(int) - 1) /* 31 on a 32-bit machine */
>>
>>/* Table to simplify conversion between mm-dd and day_in_year */
>>static daysToMonth[13] = {-1,30,60,91,121,152,183,213,244,274,305,336,366};
>>
> 
> Omitting the data type (int) was always bad style and disallowed in

OK.

> C99. The [12] entry isn't needed (and inconsistent anyway).

That last entry is there because the reverse algorithm which I mentioned 
use the same table to verify that a guessed month is correct.

> Personally I prefer to just do (m*306U+5/*or 4*/)/10, with zero-origin
> d, although it is (almost certainly) a little slower.

I think I mentioned this as well, how the IBM code I compared it to 
later used mul/div to avoid any table lookups. As you note, that is 
almost certainly slower.

> 
>>unsigned ymd2days(unsigned y, unsigned m, unsigned d)
>>{
>>	unsigned days, y100;
>>	int mask = (int) (m -= 3);
>>	mask >>= MASKSHIFT;		/* mask is -1 if jan or feb */
>>	y += mask;
>>	m += (mask & 12);		/* Make believe the year starts in March */
> 
> 
> This trick isn't completely safe; it is implementation defined in C
> what happens for right shift of a negative (signed) integer (need not
> propagate the sign, especially on a non-two's-complement machine,
> which is allowed though there are very few current examples) and
> completely undefined if there are any padding bits in the
> representation of int and hence MASKSHIFT is > actual width; this
> latter could be fixed by using >>4 which is enough (given 2sC sign
> propagation) for any value in the range used, -2 to +9.

Nice catch!

This is another case of me snipping out too much from the complete 
version: :-(

The totally portable/safe version uses unsigned operations for 
everything, and minimum length shifts to generate any required masks.
> 
> I think it's better to write what you mean; make m signed and
>   if( (m -= 3) < 0 ){ m += 12; --y; }
> and if on a given machine conditional or predicated or even masked
> operations are better than the obvious branch, a good compiler should
> choose them for you. And even if it doesn't, this code isn't very
> likely to be a performance bottleneck.

The code did start out the way you suggest, but I found that the less 
clear version resulted in better code on several systems/compilers. :-(

> 
>>	y -= STARTYEAR;
>>	y100 = y / 100;			/* Centuries for leap year calc */
>>	days = y * 365 + (y >> 2) - y100 + (y100 >> 2);
> 
> 
> Given y and y100 are unsigned (and not narrower than int), the clearer
> / 4 is equivalent to >> 2, and again a decent compiler will do that.

Decent compiler: See above.

> The y*365 term needs to be done in the wider type (by casting y and/or
> suffixing 365) on a machine where u/int is 16 bits. (Actually if the

As I specified, unsigned ints (or the unsigned type you want to use) 
must be at least 29 bits for these algorithms, which also means that 
this problem cannot occur.

Terje

PS. I do want 'decent compilers' in one particular area though: I prefer 
(but don't require) that a division of an unsigned value by a constant 
will be handled with a reciprocal multiplication. I tested (and got help 
on news:comp.arch) this on all major current platforms.

-- 
- <Terje.Mathisen at hda.hydro.com>
"almost all programming can be viewed as an exercise in caching"




More information about the questions mailing list