1 /*-
2 * SPDX-License-Identifier: BSD-3-Clause
3 *
4 * Copyright (c) 2019-2020 The DragonFly Project. All rights reserved.
5 *
6 * This code is derived from software contributed to The DragonFly Project
7 * by Aaron LI <aly@aaronly.me>
8 *
9 * Redistribution and use in source and binary forms, with or without
10 * modification, are permitted provided that the following conditions
11 * are met:
12 *
13 * 1. Redistributions of source code must retain the above copyright
14 * notice, this list of conditions and the following disclaimer.
15 * 2. Redistributions in binary form must reproduce the above copyright
16 * notice, this list of conditions and the following disclaimer in
17 * the documentation and/or other materials provided with the
18 * distribution.
19 * 3. Neither the name of The DragonFly Project nor the names of its
20 * contributors may be used to endorse or promote products derived
21 * from this software without specific, prior written permission.
22 *
23 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
24 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
25 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
26 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
27 * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
28 * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
29 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
30 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
31 * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
32 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
33 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
34 * SUCH DAMAGE.
35 *
36 * Reference:
37 * Calendrical Calculations, The Ultimate Edition (4th Edition)
38 * by Edward M. Reingold and Nachum Dershowitz
39 * 2018, Cambridge University Press
40 */
41
42 #include <err.h>
43 #include <math.h>
44 #include <stdbool.h>
45 #include <stddef.h>
46 #include <stdio.h>
47 #include <stdlib.h>
48 #include <string.h>
49
50 #include "utils.h"
51
52
53 /*
54 * Calculate the polynomial: c[0] + c[1] * x + ... + c[n-1] * x^(n-1)
55 */
56 double
poly(double x,const double * coefs,size_t n)57 poly(double x, const double *coefs, size_t n)
58 {
59 double p = 0.0;
60 double t = 1.0;
61 for (size_t i = 0; i < n; i++) {
62 p += t * coefs[i];
63 t *= x;
64 }
65 return p;
66 }
67
68 /*
69 * Use bisection search to find the inverse of the given angular function
70 * $f(x) at value $y (degrees) within time interval [$a, $b].
71 * Ref: Sec.(1.8), Eq.(1.36)
72 */
73 double
invert_angular(double (* f)(double),double y,double a,double b)74 invert_angular(double (*f)(double), double y, double a, double b)
75 {
76 static const double eps = 1e-6;
77 double x;
78
79 do {
80 x = (a + b) / 2.0;
81 if (mod_f(f(x) - y, 360) < 180.0)
82 b = x;
83 else
84 a = x;
85 } while (fabs(a-b) >= eps);
86
87 return x;
88 }
89
90
91 /*
92 * Like malloc(3) but exit if allocation fails.
93 */
94 void *
xmalloc(size_t size)95 xmalloc(size_t size)
96 {
97 void *ptr = malloc(size);
98 if (ptr == NULL)
99 errx(1, "mcalloc(%zu): out of memory", size);
100 return ptr;
101 }
102
103 /*
104 * Like calloc(3) but exit if allocation fails.
105 */
106 void *
xcalloc(size_t number,size_t size)107 xcalloc(size_t number, size_t size)
108 {
109 void *ptr = calloc(number, size);
110 if (ptr == NULL)
111 errx(1, "xcalloc(%zu, %zu): out of memory", number, size);
112 return ptr;
113 }
114
115 /*
116 * Like realloc(3) but exit if allocation fails.
117 */
118 void *
xrealloc(void * ptr,size_t size)119 xrealloc(void *ptr, size_t size)
120 {
121 ptr = realloc(ptr, size);
122 if (ptr == NULL)
123 errx(1, "xrealloc: out of memory (size: %zu)", size);
124 return ptr;
125 }
126
127 /*
128 * Like strdup(3) but exit if fail.
129 */
130 char *
xstrdup(const char * str)131 xstrdup(const char *str)
132 {
133 char *p = strdup(str);
134 if (p == NULL)
135 errx(1, "xstrdup: out of memory (length: %zu)", strlen(str));
136 return p;
137 }
138
139
140 /*
141 * Linked list implementation
142 */
143
144 struct node {
145 char *name;
146 void *data;
147 struct node *next;
148 };
149
150 /*
151 * Create a new list node with the given $name and $data.
152 */
153 struct node *
list_newnode(char * name,void * data)154 list_newnode(char *name, void *data)
155 {
156 struct node *newp;
157
158 newp = xcalloc(1, sizeof(*newp));
159 newp->name = name;
160 newp->data = data;
161
162 return newp;
163 }
164
165 /*
166 * Add $newp to the front of list $listp.
167 */
168 struct node *
list_addfront(struct node * listp,struct node * newp)169 list_addfront(struct node *listp, struct node *newp)
170 {
171 newp->next = listp;
172 return newp;
173 }
174
175 /*
176 * Lookup the given $name in the list $listp.
177 * The $cmp function compares two names and return 0 if they equal.
178 * Return the associated data with the found node, otherwise NULL.
179 */
180 bool
list_lookup(struct node * listp,const char * name,int (* cmp)(const char *,const char *),void ** data_out)181 list_lookup(struct node *listp, const char *name,
182 int (*cmp)(const char *, const char *), void **data_out)
183 {
184 for ( ; listp; listp = listp->next) {
185 if ((*cmp)(name, listp->name) == 0) {
186 if (data_out)
187 *data_out = listp->data;
188 return true;
189 }
190 }
191
192 return false;
193 }
194
195 /*
196 * Free all nodes of list $listp.
197 */
198 void
list_freeall(struct node * listp,void (* free_name)(void *),void (* free_data)(void *))199 list_freeall(struct node *listp,
200 void (*free_name)(void *),
201 void (*free_data)(void *))
202 {
203 struct node *cur;
204
205 while (listp) {
206 cur = listp;
207 listp = listp->next;
208 if (free_name)
209 (*free_name)(cur->name);
210 if (free_data)
211 (*free_data)(cur->data);
212 free(cur);
213 }
214 }
215