算法

kernel/time.c中的mktime算法（下）

2007年12月09日 Sunday 于 6:01 pm · 发表在 C, 内核学习, 操作系统, 算法, 编程

好，现在我们已经得到一个公式来计算mon月之前已经过去的日子了：
X=year/4-year/100+year/400+(year-1)*365+30*mon-30+(mon+mon/7)/2+day-1
现在我们来计算一下公元1年1月1日：
经过下面这段代码的转换之后，year=0，mon=11，day=1.。

  1. if (0 >= (int) (mon -= 2)) {
  2.         mon += 12;    /* Puts Feb last since it has leap day */
  3.         year -= 1;
  4. }

代入表达式：0-0+0+（0-1）*365 + 30 *11 -30 + （11+11/7）/2 + 1-1=365-306=-59.
这个59显而易见的是由我们将1,2月置后造成的，所以这个公式需要加上一个修正值：59.
再减去1970年离公元1年的日子719162,那么我们的mktime就完成了。
改正后的公式为：
X=year/4-year/100+year/400+(year-1)*365+30*mon-30+(mon+mon/7)/2+day-1 + 59 - 719162
让我们对这个公式进行整理吧，整理后得到：
X=year/4-year/100+year/400+year*365 + 214*mon/7 + day - 719499
和linux源码中的mktime公式并不一样！！不是原来的367*mon/12！

为什么会有这样的区别呢？让我们来回忆一样推导g(mon)的第三步：
g(mon)=30*mon -30 + (mon + mon/7)/2;
事实上，大家会发现，在这儿，这个表达式并不是唯一的！下面这个表达式也是正确的：
g(mon)=30*mon -30 + (mon + mon/6)/2;
让我们用新的g(mon)代入最后的式子，你会惊喜的发现得到的是下面的式子：
year/4-year/100+year/400+year*365 + 367*mon/12 + day - 719499
正是kernel/time.c中的mktime表达式！
阅读这篇文章的剩余部分 »

(14) 条评论

kernel/time.c中的mktime算法（上）

2007年12月09日 Sunday 于 5:40 pm · 发表在 C, 内核学习, 操作系统, 算法, 编程

去年在acstar的限时比赛时写过一个程序，是计算某日到2000年1月1日的天数，当时我写的算法用了大概50行,使用的算法很烂。今天在linux内核源码中看到mktime的时候，很清楚折服于它如此简单的算法(据说是Gauss算法)，同时犯糊涂。

我将源码摘抄如下：
kernel/time.c

  1. /* Converts Gregorian date to seconds since 1970-01-01 00:00:00.
  2. * Assumes input in normal date format, i.e. 1980-12-31 23:59:59
  3. * => year=1980, mon=12, day=31, hour=23, min=59, sec=59.
  4. *
  5. * [For the Julian calendar (which was used in Russia before 1917,
  6. * Britain & colonies before 1752, anywhere else before 1582,
  7. * and is still in use by some communities) leave out the
  8. * -year/100+year/400 terms, and add 10.]
  9. *
  10. * This algorithm was first published by Gauss (I think).
  11. *
  12. * WARNING: this function will overflow on 2106-02-07 06:28:16 on
  13. * machines were long is 32-bit! (However, as time_t is signed, we
  14. * will already get problems at other places on 2038-01-19 03:14:08)
  15. */
  16. unsigned long
  17. mktime(const unsigned int year0, const unsigned int mon0,
  18.        const unsigned int day, const unsigned int hour,
  19.        const unsigned int min, const unsigned int sec)
  20. {
  21.     unsigned int mon = mon0, year = year0;
  22.  
  23.     /* 1..12 -> 11,12,1..10 */
  24.     if (0 >= (int) (mon -= 2)) {
  25.         mon += 12;    /* Puts Feb last since it has leap day */
  26.         year -= 1;
  27.     }
  28.  
  29.     return ((((unsigned long)
  30.           (year/4 - year/100 + year/400 + 367*mon/12 + day) +
  31.           year*365 - 719499
  32.         )*24 + hour /* now have hours */
  33.       )*60 + min /* now have minutes */
  34.     )*60 + sec; /* finally seconds */
  35. }

阅读这篇文章的剩余部分 »

没有评论