thermistor: Add generic linear interpolation algorithm

The existing algorithm makes several assumptions for a particular
thermistor circuit. This patch introduces a more generic version
that can be used for multiple thermistors on a single board.

The idea is to approximate a curve produced by solving for voltage
measued by an ADC using the Steinhart-Hart equation. For a straight
line one only needs two data points. For a steady curve data
points can be distributed evenly. For the most part, though, data
points should be provided after a significant change in slope.

More data points give more accuracy at the expense of memory, and
we mostly only care about accuracy in the range between "warm"
and "too hot" so only a few data points should be used.

BUG=chrome-os-partner:54818
BRANCH=none
TEST=added unit test, needs real testing

Change-Id: I046e61dbfd1e8c26c2a533777f222f5413938556
Signed-off-by: David Hendricks <dhendrix@chromium.org>
Reviewed-on: https://chromium-review.googlesource.com/344781
Reviewed-by: Shawn N <shawnn@chromium.org>

3 files changed, 199 insertions, 0 deletions

diff --git a/driver/temp_sensor/thermistor.h b/driver/temp_sensor/thermistor.h
index 3bb5335ddd..0f42742352 100644
--- a/driver/temp_sensor/thermistor.h
+++ b/driver/temp_sensor/thermistor.h
@@ -8,6 +8,44 @@
 #ifndef __CROS_EC_TEMP_SENSOR_THERMISTOR_H
 #define __CROS_EC_TEMP_SENSOR_THERMISTOR_H
 
+struct thermistor_data_pair {
+	uint8_t mv;	/* Scaled voltage level at ADC (in mV) */
+	uint8_t temp;	/* Temperature in Celsius */
+};
+
+struct thermistor_info {
+	uint8_t scaling_factor;	/* Scaling factor for voltage in data pair. */
+	uint8_t num_pairs;	/* Number of data pairs. */
+
+	/*
+	 * Values between given data pairs will be calculated as points on
+	 * a line. Pairs can be derived using the Steinhart-Hart equation.
+	 *
+	 * Guidelines for data sets:
+	 * - Must contain at least two pairs.
+	 * - First and last pairs are the min and max.
+	 * - Pairs must be sorted in ascending order.
+	 * - 5 pairs should provide reasonable accuracy in most cases. Use
+	 *   points where the slope changes significantly or to recalibrate
+	 *   the algorithm if needed.
+	 */
+	const struct thermistor_data_pair *data;
+};
+
+/**
+ * @brief Calculate temperature using linear interpolation of data points.
+ *
+ * Given a set of datapoints, the algorithm will calculate the "step" in
+ * between each one in order to interpolate missing entries.
+ *
+ * @param mv	Value read from ADC (in millivolts).
+ * @param info	Reference data set and info.
+ *
+ * @return	temperature in C
+ */
+int thermistor_linear_interpolate(uint16_t mv,
+				const struct thermistor_info *info);
+
 /**
  * ncp15wb temperature conversion routine.
  *
diff --git a/driver/temp_sensor/thermistor_ncp15wb.c b/driver/temp_sensor/thermistor_ncp15wb.c
index 51e884ed35..64ba9fea40 100644
--- a/driver/temp_sensor/thermistor_ncp15wb.c
+++ b/driver/temp_sensor/thermistor_ncp15wb.c
@@ -98,3 +98,54 @@ int ncp15wb_calculate_temp(uint16_t adc)
 
 	return temp;
 }
+
+int thermistor_linear_interpolate(uint16_t mv,
+		const struct thermistor_info *info)
+{
+	const struct thermistor_data_pair *data = info->data;
+	int v0, v1, t0, t1, num_steps;
+	int head, tail, mid;
+
+	/* We need at least two points to form a line. */
+	ASSERT(info->num_pairs >= 2);
+
+	/*
+	 * If input value is out of bounds return the lowest or highest
+	 * value in the data sets provided.
+	 */
+	if (mv < data[0].mv * info->scaling_factor)
+		return data[0].temp;
+	else if (mv > data[info->num_pairs - 1].mv * info->scaling_factor)
+		return data[info->num_pairs - 1].temp;
+
+	head = 0;
+	tail = info->num_pairs - 1;
+	while (head != tail) {
+		mid = (head + tail) / 2;
+		v0 = data[mid].mv * info->scaling_factor;
+		v1 = data[mid + 1].mv * info->scaling_factor;
+
+		if ((mv >= v0) && (mv <= v1))
+			break;
+		else if (mv < v0)
+			tail = mid;
+		else if (mv > v1)
+			head = mid + 1;
+	}
+
+	t0 = data[mid].temp;
+	t1 = data[mid + 1].temp;
+
+	/*
+	 * The obvious way of doing this is to figure out how many mV per
+	 * degree are in between the two points (mv_per_deg_c), and then how
+	 * many of those exist between the input voltage and lower voltage (v0):
+	 *   1. mv_per_deg_c = (v1 - v0) / (t1 - t0)
+	 *   2. num_steps = (mv - v0) / mv_per_deg_c
+	 *   3. result = t0 + num_steps
+	 *
+	 * Combine #1 and #2 to mitigate precision loss due to integer division.
+	 */
+	num_steps = ((mv - v0) * (t1 - t0)) / (v1 - v0);
+	return t0 + num_steps;
+}
diff --git a/test/thermal.c b/test/thermal.c
index 6e95d37f83..ecabaf1ee1 100644
--- a/test/thermal.c
+++ b/test/thermal.c
@@ -7,6 +7,7 @@
 
 #include "common.h"
 #include "console.h"
+#include "driver/temp_sensor/thermistor.h"
 #include "fan.h"
 #include "hooks.h"
 #include "host_command.h"
@@ -532,6 +533,114 @@ static int test_ncp15wb_adc_to_temp(void)
 	return EC_SUCCESS;
 }
 
+#define THERMISTOR_SCALING_FACTOR 13
+static int test_thermistor_linear_interpolate(void)
+{
+	int i, t, t0;
+	uint16_t mv;
+	/* Simple test case - a straight line. */
+	struct thermistor_data_pair line_data[] = {
+		{ 0, 0 }, { 100, 100 }
+	};
+	struct thermistor_info line_info = {
+		.scaling_factor = 1,
+		.num_pairs = ARRAY_SIZE(line_data),
+		.data = line_data,
+	};
+	/*
+	 * Modelled test case - Data derived from Seinhart-Hart equation in a
+	 * resistor divider circuit with Vdd=3300mV, R = 51.1Kohm, and Murata
+	 * NCP15WB-series thermistor (B = 4050, T0 = 298.15, nominal
+	 * resistance (R0) = 47Kohm).
+	 */
+	struct thermistor_data_pair data[] = {
+		{ 787 / THERMISTOR_SCALING_FACTOR, 0 },
+		{ 1142 / THERMISTOR_SCALING_FACTOR, 10 },
+		{ 1528 / THERMISTOR_SCALING_FACTOR, 20 },
+		{ 1901 / THERMISTOR_SCALING_FACTOR, 30 },
+		{ 2229 / THERMISTOR_SCALING_FACTOR, 40 },
+		{ 2497 / THERMISTOR_SCALING_FACTOR, 50 },
+		{ 2703 / THERMISTOR_SCALING_FACTOR, 60 },
+		{ 2857 / THERMISTOR_SCALING_FACTOR, 70 },
+		{ 2970 / THERMISTOR_SCALING_FACTOR, 80 },
+		{ 3053 / THERMISTOR_SCALING_FACTOR, 90 },
+		{ 3113 / THERMISTOR_SCALING_FACTOR, 100 },
+	};
+	struct thermistor_info info = {
+		.scaling_factor = THERMISTOR_SCALING_FACTOR,
+		.num_pairs = ARRAY_SIZE(data),
+		.data = data,
+	};
+	/*
+	 * Reference data points to compare accuracy, taken from same set
+	 * of derived values but at temp - 1, temp + 1, and in between.
+	 */
+	struct {
+		uint16_t mv;	/* not scaled */
+		int temp;
+	} cmp[] = {
+		{ 820, 1 },  { 958, 5 }, { 1104, 9 },
+		{ 1180, 11 }, { 1334, 15 }, { 1489, 19 },
+		{ 1566, 21 }, { 1718, 25 }, { 1866, 29 },
+		{ 1937, 31 }, { 2073, 35 }, { 2199, 39 },
+		{ 2259, 41 }, { 2371, 45 }, { 2473, 49 },
+		{ 2520, 51 }, { 2607, 55 }, { 2685, 59 },
+		{ 2720, 61 }, { 2786, 65 }, { 2844, 69 },
+		{ 2870, 71 }, { 2918, 75 }, { 2960, 79 },
+		{ 2980, 81 }, { 3015, 85 }, { 3045, 89 },
+		{ 3060, 91 }, { 3085, 95 }, { 3107, 99 },
+	};
+
+	/* Return lowest temperature in data set if voltage is too low. */
+	mv = (data[0].mv * info.scaling_factor) - 1;
+	t = thermistor_linear_interpolate(mv, &info);
+	TEST_ASSERT(t == data[0].temp);
+
+	/* Return highest temperature in data set if voltage is too high. */
+	mv = (data[info.num_pairs - 1].mv * info.scaling_factor) + 1;
+	t = thermistor_linear_interpolate(mv, &info);
+	TEST_ASSERT(t == data[info.num_pairs - 1].temp);
+
+	/* Simple line test */
+	for (mv = line_data[0].mv;
+		mv < line_data[line_info.num_pairs - 1].mv;
+		mv++) {
+		t = thermistor_linear_interpolate(mv, &line_info);
+		TEST_ASSERT(mv == t);
+	}
+
+	/*
+	 * Verify that calculated temperature monotonically
+	 * increases with voltage (0-5V, 10mV steps).
+	 */
+	for (mv = data[0].mv * info.scaling_factor, t0 = data[0].temp;
+		mv < data[info.num_pairs - 1].mv;
+		mv += 10) {
+		int t1 = thermistor_linear_interpolate(mv, &info);
+
+		TEST_ASSERT(t1 >= t0);
+		t0 = t1;
+	}
+
+	/* Verify against modelled data, +/- 1C due to scaling. */
+	for (i = 0; i < info.num_pairs; i++) {
+		mv = data[i].mv * info.scaling_factor;
+
+		t = thermistor_linear_interpolate(mv, &info);
+		TEST_ASSERT(t >= data[i].temp - 1 && t <= data[i].temp + 1);
+	}
+
+	/*
+	 * Verify data points that are interpolated by algorithm, allowing
+	 * 1C of inaccuracy.
+	 */
+	for (i = 0; i < ARRAY_SIZE(cmp); i++) {
+		t = thermistor_linear_interpolate(cmp[i].mv, &info);
+		TEST_ASSERT(t >= cmp[i].temp - 1 && t <= cmp[i].temp + 1);
+	}
+
+	return EC_SUCCESS;
+}
 
 void run_test(void)
 {
@@ -545,5 +654,6 @@ void run_test(void)
 	RUN_TEST(test_several_limits);
 
 	RUN_TEST(test_ncp15wb_adc_to_temp);
+	RUN_TEST(test_thermistor_linear_interpolate);
 	test_print_result();
 }