Tor
0.4.6.0-alpha-dev
lib
math
laplace.c
Go to the documentation of this file.
1
/* Copyright (c) 2003, Roger Dingledine
2
* Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
3
* Copyright (c) 2007-2020, The Tor Project, Inc. */
4
/* See LICENSE for licensing information */
5
6
/**
7
* \file laplace.c
8
*
9
* \brief Implements a Laplace distribution, used for adding noise to things.
10
**/
11
12
#include "orconfig.h"
13
#include "
lib/math/laplace.h
"
14
#include "
lib/math/fp.h
"
15
16
#include "
lib/log/util_bug.h
"
17
18
#include <math.h>
19
#include <stdlib.h>
20
21
/** Transform a random value <b>p</b> from the uniform distribution in
22
* [0.0, 1.0[ into a Laplace distributed value with location parameter
23
* <b>mu</b> and scale parameter <b>b</b>. Truncate the final result
24
* to be an integer in [INT64_MIN, INT64_MAX]. */
25
int64_t
26
sample_laplace_distribution
(
double
mu,
double
b,
double
p)
27
{
28
double
result;
29
tor_assert
(p >= 0.0 && p < 1.0);
30
31
/* This is the "inverse cumulative distribution function" from:
32
* https://en.wikipedia.org/wiki/Laplace_distribution */
33
if
(p <= 0.0) {
34
/* Avoid taking log(0.0) == -INFINITY, as some processors or compiler
35
* options can cause the program to trap. */
36
return
INT64_MIN;
37
}
38
39
result = mu - b * (p > 0.5 ? 1.0 : -1.0)
40
*
tor_mathlog
(1.0 - 2.0 * fabs(p - 0.5));
41
42
return
clamp_double_to_int64
(result);
43
}
44
45
/** Add random noise between INT64_MIN and INT64_MAX coming from a Laplace
46
* distribution with mu = 0 and b = <b>delta_f</b>/<b>epsilon</b> to
47
* <b>signal</b> based on the provided <b>random</b> value in [0.0, 1.0[.
48
* The epsilon value must be between ]0.0, 1.0]. delta_f must be greater
49
* than 0. */
50
int64_t
51
add_laplace_noise
(int64_t signal_,
double
random_,
double
delta_f,
52
double
epsilon)
53
{
54
int64_t noise;
55
56
/* epsilon MUST be between ]0.0, 1.0] */
57
tor_assert
(epsilon > 0.0 && epsilon <= 1.0);
58
/* delta_f MUST be greater than 0. */
59
tor_assert
(delta_f > 0.0);
60
61
/* Just add noise, no further signal */
62
noise =
sample_laplace_distribution
(0.0,
63
delta_f / epsilon,
64
random_);
65
66
/* Clip (signal + noise) to [INT64_MIN, INT64_MAX] */
67
if
(noise > 0 && INT64_MAX - noise < signal_)
68
return
INT64_MAX;
69
else
if
(noise < 0 && INT64_MIN - noise > signal_)
70
return
INT64_MIN;
71
else
72
return
signal_ + noise;
73
}
add_laplace_noise
int64_t add_laplace_noise(int64_t signal_, double random_, double delta_f, double epsilon)
Definition:
laplace.c:51
tor_assert
#define tor_assert(expr)
Definition:
util_bug.h:102
sample_laplace_distribution
int64_t sample_laplace_distribution(double mu, double b, double p)
Definition:
laplace.c:26
util_bug.h
Macros to manage assertions, fatal and non-fatal.
fp.h
Header for fp.c.
laplace.h
Header for laplace.c.
clamp_double_to_int64
int64_t clamp_double_to_int64(double number)
Definition:
fp.c:61
tor_mathlog
double tor_mathlog(double d)
Definition:
fp.c:22
Generated by
1.8.20