#+TITLE: R-Line
* Introduction
R-Line is a random line segment generator. It
produces random values at regular rate, and then
linearly interpolates between them. The algorithm has
audio-rate parametric control of both the range
and rate of change for generated values.

This algorithm is a great little control signal generator
that can add a bit of zest to an otherwise
static parameter in a patch. It's a very efficient way to
add a warm organic feel to a patch.
* Notable Implementation Details
This particular algorithm uses a fixed-point phasor similar
to the ones seen in @!(ref "osc")!@ and @!(ref "fmpair")!@.
Fixed point has very good numerical stability, which makes
it ideal for a phasor algorithm.

To keep things more portable, R-Line implements its own
pseudo-Random Number Generator (pRNG), using a common
algorithm generating random values known as
[[https://en.wikipedia.org/wiki/Linear_congruential_generator][Linear Congruential Generator]], or an LCG. This is
what most =rand= function
implementations use under the hood. The modulus, multiplier,
and and increment values come from the Microsoft
Visual/Quick C/C++ library (as found on Wikipedia).
* Tangled Files
R-Line tangles to a C file and a header file.

The C file =rline.c= contains the core implementation
code.

#+NAME: rline.c
#+BEGIN_SRC c :tangle rline.c
#include <math.h>
#define SK_RLINE_PRIV
#include "rline.h"
<<macros>>
<<funcs>>
#+END_SRC

The header file =rline.h= contains forward function
declarations. When =SK_RLINE_PRIV= is enabled, the structs
are exposed. Otherwise, they are left as opaque.

#+NAME: rline.h
#+BEGIN_SRC c :tangle rline.h
#ifndef SK_RLINE_H
#define SK_RLINE_H

#ifndef SKFLT
#define SKFLT float
#endif

<<typedefs>>
<<funcdefs>>

#ifdef SK_RLINE_PRIV
<<structs>>
#endif
#endif
#+END_SRC
* Core Struct
The core struct is called =sk_rline=.

#+NAME: typedefs
#+BEGIN_SRC c
typedef struct sk_rline sk_rline;
#+END_SRC

#+NAME: structs
#+BEGIN_SRC c
struct sk_rline {
    <<sk_rline>>
};
#+END_SRC
* Constants and Variables
The value from the LCG is often scaled to be normalized
between 0 and 1. The constant required for this is
$1/(2^31 - 1$, or =1/((1L<<31) - 1)=. This value is
stored in a constant.

#+NAME: sk_rline
#+BEGIN_SRC c
SKFLT rngscale;
#+END_SRC

#+NAME: set_random_scaler
#+BEGIN_SRC c
rl->rngscale = 1.0 / ((1L<<31) - 1);
#+END_SRC

The current state of the random number generator is stored
as an integer =rng=. It is initialized to be =seed=.

#+NAME: sk_rline
#+BEGIN_SRC c
int rng;
#+END_SRC

#+NAME: init
#+BEGIN_SRC c
rl->rng = seed;
<<set_random_scaler>>
<<generate_initial_values>>
#+END_SRC

The fixed point phasor has two major constants: the maximum
length, as well as the masking value. Detailed explanation
of these are beyond the scope of this document. For more
information, consult the relevant sections in
@!(ref "osc")!@.

#+NAME: macros
#+BEGIN_SRC c
#define SK_RLINE_PHSLEN 0x1000000L
#define SK_RLINE_PHSMSK 0xFFFFFFL
#+END_SRC

The variable =maxlens= is maximum phasor length converted to
units of seconds by dviding it by the sampling rate.
Multipyling this value with a frequency will return an
increment value in units of phasor, which is used
as the phasor increment value.

#+NAME: sk_rline
#+BEGIN_SRC c
SKFLT maxlens;
#+END_SRC

#+NAME: init
#+BEGIN_SRC c
rl->maxlens = (SKFLT)SK_RLINE_PHSLEN / sr;
#+END_SRC

Phase position is stored in an unsigned long called
=phspos=. When it needs to be converted for use in floating
point operations , the constant =scale= is used.

#+NAME: sk_rline
#+BEGIN_SRC c
unsigned long phasepos;
SKFLT scale;
#+END_SRC

#+NAME: init
#+BEGIN_SRC c
rl->phasepos = 0;
#+END_SRC

The scale value works by normalizing to be in the range 0-1
by dividing by the max phase length =SK_RLINE_PHSLEN=, then
scaling it to be the difference between the start/end point
values. Doing this shaves off a divide operation later.

#+NAME: calculate_initial_scale
#+BEGIN_SRC c
rl->scale = (rl->end - rl->start) / SK_RLINE_PHSLEN;
#+END_SRC

A line has two points: a start point, and an end point.
These are stored as normalized floating point variables
=start= and =end=, and then are dynamically scaled to the
=min= and =max= values during computation.

#+NAME: sk_rline
#+BEGIN_SRC c
SKFLT start;
SKFLT end;
#+END_SRC

#+NAME: generate_initial_values
#+BEGIN_SRC c
rl->rng = LCG(rl->rng);
rl->start = RNG(rl->rng) * rl->rngscale;
rl->rng = LCG(rl->rng);
rl->end = RNG(rl->rng) * rl->rngscale;
<<calculate_initial_scale>>
#+END_SRC
* Linear Congruential Generator
An internal
[[https://en.wikipedia.org/wiki/Linear_congruential_generator][Linear Congruential Generator]] is
used to generate sequences of pseudo-random numbers.

It is the following equation

$$
y(n) = ((y(n - 1) * a + c) \gg 1)
\& m
$$

Where $m$ is the masking value =0x7ffffff=, $a$ is a
=multiplier=, and $c$ is the =increment=. In this
implementation, $a$ will be =0x343fd=, and $c$ will be
=0x2693ec3=. These constants come from the wikipedia page
on LCGs, and originate the Microsoft Visual C/C++ standard
library.

The LCG here can be implemented as a stateless function or
macro. In this case, we will go with the macro.

#+NAME: macros
#+BEGIN_SRC c
#define LCG(y) (y * 0x343fd + 0x269ec3)
#+END_SRC

The =LCG= operation only computes the next state state of
the random-number generator. To actually get it within the
correct bounds for this sytem, it has to be right-shifted
to knock it down 1 bit, then masked by =0x7ffffff= as a kind
of modulo operation.

This macro operation =RNG= assumes that =y= is the current
state of the LCG.
#+NAME: macros
#+BEGIN_SRC c
#define RNG(y) ((y >> 1) & 0x7fffffff)
#+END_SRC
* Initialization
Initialization is done with =sk_rline_init=.

The main things needed for initialization are the sampling
rate =sr=, as well as the initial seed value for the random
number generator.

#+NAME: funcdefs
#+BEGIN_SRC c
void sk_rline_init(sk_rline *rl, int sr, int seed);
#+END_SRC

#+NAME: funcs
#+BEGIN_SRC c
void sk_rline_init(sk_rline *rl, int sr, int seed)
{
    <<init>>
}
#+END_SRC
* Parameters
** Minimum value
Set with =sk_rline_min=.

#+NAME: funcdefs
#+BEGIN_SRC c
void sk_rline_min(sk_rline *rl, SKFLT min);
#+END_SRC

#+NAME: funcs
#+BEGIN_SRC c
void sk_rline_min(sk_rline *rl, SKFLT min)
{
    rl->min = min;
}
#+END_SRC

#+NAME: sk_rline
#+BEGIN_SRC c
SKFLT min;
#+END_SRC

Initialized to be 0.

#+NAME: init
#+BEGIN_SRC c
sk_rline_min(rl, 0);
#+END_SRC
** Maximum value
Set with =sk_rline_max=.

#+NAME: funcdefs
#+BEGIN_SRC c
void sk_rline_max(sk_rline *rl, SKFLT max);
#+END_SRC

#+NAME: funcs
#+BEGIN_SRC c
void sk_rline_max(sk_rline *rl, SKFLT max)
{
    rl->max= max;
}
#+END_SRC

#+NAME: sk_rline
#+BEGIN_SRC c
SKFLT max;
#+END_SRC

Initialized to be 1.

#+NAME: init
#+BEGIN_SRC c
sk_rline_max(rl, 1);
#+END_SRC
** Rate
Set with =sk_rline_rate=.

#+NAME: funcdefs
#+BEGIN_SRC c
void sk_rline_rate(sk_rline *rl, SKFLT rate);
#+END_SRC

#+NAME: funcs
#+BEGIN_SRC c
void sk_rline_rate(sk_rline *rl, SKFLT rate)
{
    rl->rate= rate;
}
#+END_SRC

#+NAME: sk_rline
#+BEGIN_SRC c
SKFLT rate;
#+END_SRC

Initialized to be an arbitrary default value 1.

#+NAME: init
#+BEGIN_SRC c
sk_rline_rate(rl, 1);
#+END_SRC
* Computing a sample
A single sample is computed with =sk_rline_tick=.

#+NAME: funcdefs
#+BEGIN_SRC c
SKFLT sk_rline_tick(sk_rline *rl);
#+END_SRC

#+NAME: funcs
#+BEGIN_SRC c
SKFLT sk_rline_tick(sk_rline *rl)
{
    SKFLT out;

    out = 0;

    <<compute_current_sample>>
    <<update_phase>>
    <<generate_next_line_segment>>

    return out;
}
#+END_SRC

Compute the current sample. The line interpolation is
calculated in a normalized space, then scaled to be
in the min/max range. Doing it this way allows the min/max
values to be dynamically changed over time without having
to wait for the next line.

The normalized output can be computed with the expression:

$$
y = x_1 + pc
$$

Where $x_1$ is the starting point of the line, $p$ is
the current phase increment, represented in fixed point, and
$c$ is the constant that normalizes and scales the phase to
be the amount of progress to value $x_2$.

#+NAME: compute_current_sample
#+BEGIN_SRC c
out = rl->start + rl->phasepos*rl->scale;
out = out * (rl->max - rl->min) + rl->min;
#+END_SRC


Update phase position. The phase is updated by incrementing
it by a amount obtained by multiplying the frequency by the
maximum phase length in units of seconds. How this works is
beyond the scope of this document, but is explained in @!(ref
"osc")!@.

#+NAME: update_phase
#+BEGIN_SRC c
rl->phasepos += floor(rl->rate * rl->maxlens);
#+END_SRC

Generate next line segment. Preparation for a new line
segment happens when the phase of the phasor reaches the
end, and is greater than or equal to the max length.
The phasor is masked in order to filter out upper
bits and allow the lower bits to roll over. The the starting
value is set to be the current end value, and a new end
value is obtained using the random number generator.

After the new points have been obtained, the constant used
to normalize + scale the phasor value is computed. Dividing
by the maximum phasor length normalizes the phasor to be in
range 0 and 1. Multiplying by the difference of the two
segment values scales this value to be in the correct range.
This constant is useful because it shaves off a divide
operation, which has traditionally been a costly arithmetic
computatoin compared to a multiply.

#+NAME: generate_next_line_segment
#+BEGIN_SRC c
if (rl->phasepos >= SK_RLINE_PHSLEN) {
    rl->phasepos &= SK_RLINE_PHSMSK;
    rl->start = rl->end;
    rl->rng = LCG(rl->rng);
    rl->end = RNG(rl->rng) * rl->rngscale;
    rl->scale = (rl->end - rl->start) / SK_RLINE_PHSLEN;
}
#+END_SRC