您的位置: 首页  >  文章  >  Linux内核中mktime()函数算法分析

Linux内核中mktime()函数算法分析

分类: 文章 • 2024-07-29 11:37:28

Linux内核中的mktime()函数位于kernel/time.c内

该函数主要用于内核启动时，将CMOS中的 年-月-日 时:分:秒 信息转换为距离1970-01-01 00:00:00的秒数

具体定义如下：

  1. unsignedlong
  2. mktime(constunsignedintyear0,constunsignedintmon0,
  3. constunsignedintday,constunsignedinthour,
  4. constunsignedintmin,constunsignedintsec)
  5. {
  6. unsignedintmon=mon0,year=year0;
  8. /*1..12->11,12,1..10*/
  9. if(0>=(int)(mon-=2)){
  10. mon+=12;/*PutsFeblastsinceithasleapday*/
  11. year-=1;
  12. }
  14. return((((unsignedlong)
  15. (year/4-year/100+year/400+367*mon/12+day)+
  16. year*365-719499
  17. )*24+hour/*nowhavehours*/
  18. )*60+min/*nowhaveminutes*/
  19. )*60+sec;/*finallyseconds*/
  20. }

注意到计算的结果为相对时间

具体的计算方法也进行了两次相对运算

1、将时间轴整体后移2个月，以方便闰年的计算

原来相对1970-01-01 00:00:00，变成了相对1969-11-01 00:00:00

被计算的参数时间数值上也相对移位减小

但是这并不影响原来的相对差值

2、时间基准点为1-1-1 00:00:00（移位2个月后的）

即分别计算参数时间与基准点的秒数A

和1969-11-01 00:00:00与基准点的秒数B

然后A - B即最终结果

因为 天 时:分:秒 的相对基准固定

故算法中主要关心年份和月份到天数的转换

先考虑通用的 年-月-日 转天数的计算方法

例如：计算year-mon-day距离公元1-1-1的天数

公式可以表示为：(year - 1) * 365 + f(mon) + (day - 1) + leap_days

f(mon)表示关于mon的一个函数关系

可以使用类似如下的代码实现

  1. intmon_passed_2days(intm)
  2. {
  3. intx=0;
  5. switch(m-1){
  6. default:
  7. break;
  8. case11:
  9. x+=30;
  10. case10:
  11. x+=31;
  12. case9:
  13. x+=30;
  14. case8:
  15. x+=31;
  16. case7:
  17. x+=31;
  18. case6:
  19. x+=30;
  20. case5:
  21. x+=31;
  22. case4:
  23. x+=30;
  24. case3:
  25. x+=31;
  26. case2:
  27. x+=28;
  28. case1:
  29. x+=31;
  30. }
  31. returnx;
  32. }

leap_days表示对闰年天数的修正

在计算闰年所增加的天数时使用公式：(year - 1) / 4 - (year - 1) / 100 + (year - 1) / 400

式中各个除法运算 / 后，还需向下取整，表达式中省略了符号 [ ] ，下同

这里减1是因为当前的year补闰1天需要根据月份进行单独判断处理

可以使用类似如下的代码

  1. if(mon>2&&is_leap_year(year)){
  2. days+=1;
  3. }

当将时间轴移位2个月

将闰2月变成了1年之中的最后一个月份时

此时将闰年需要修正的一天记为该年之中的0月，这个月要么是0天，要么是1天

那么原来为当前年进行2月修正的判断便成为了

  1. if(mon>0&&is_leap_year(year)){
  2. days+=1;
  3. }

显然mon > 0总是成立

这样对所有闰年的修正表达式便简化成为了：year / 4 - year / 100 + year / 400


这便是相对移位2个月带来的好处

以下计算为移月后数据

移月后，1年之中的天/月分布为

天/月分布
1 2 3 4 5 6 7 8 9 10 11 12
31 30 31 30 31 31 30 31 30 31 31 28


计算1969-11-01距离1-1-1的天数

公式：days1 = (1969 - 1) * 365 + f(11) + (1 - 1) + 1969 / 4- 1969 / 100 + 1969 / 400

根据月份流逝对应的天数可以产生如下的表格

月份对应的流逝天数
1 2 3 4 5 6 7 8 9 10 11 12
0 31 61 92 122 153 184 214 245 275 306 337

计算year-mon-day距离1-1-1的天数

公式：days2 = (year - 1) * 365 + f(mon) + (day - 1) +year / 4-year / 100 +year / 400

合并两式：

days2 - days1 = year * 365 + f(mon) + day +year / 4-year / 100 +year / 400 - (1969 * 365 + 306 + 477)

= year * 365 + f(mon) + day +year / 4-year / 100 +year / 400 - 719469

f(11)可以从表中查出

但是当mon未知时，则需要想办法确定一个函数关系来进行f(mon)的计算

如果假定每个月都为30天，则月份流逝天数可以表示为：(mon - 1) * 30

然后在上面的月份流逝表基础上生成一个修正表即可

月份天数流逝修正表
1 2 3 4 5 6 7 8 9 10 11 12
0 1 1 2 2 3 4 4 5 5 6 7

这样days2 - days1便转化为：

year * 365 + g(mon) + mon * 30+ day +year / 4-year / 100 +year / 400 - 719499

这里的函数关系g(mon)还需要确定

将月份流逝修正表中的数据画成图表

Linux内核中mktime()函数算法分析

考虑到修正值都是整数，那么只需要找出一个斜率合适的直线，保证各个X点的Y值不超过向上取整的值即可

每个X点斜率的可能范围，左闭右开

斜率范围
1 2 3 4 5 6 7 8 9 10 11 12
[0, 1) [1/2, 1) [1/3, 2/3) [1/2, 3/4) [2/5, 3/5) [3/6, 4/6) [4/7, 5/7) [4/8, 5,8) [5/9, 6/9) [5/10, 6/10) [6/11, 7/11) [7/12. 8/12)

综合各个区间范围

最终的修正系数落在区间[7/12, 3/5)内

因此这样的修正系数是无穷的

内核中使用了7/12这个数

那么g(mon)便可表示为7/12 * mon

如此便得到了最终的表达式

  1. return((((unsignedlong)
  2. (year/4-year/100+year/400+367*mon/12+day)+
  3. year*365-719499
  4. )*24+hour/*nowhavehours*/
  5. )*60+min/*nowhaveminutes*/
  6. )*60+sec;/*finallyseconds*/



相关推荐