# R-Line

This is a `sndkit`

algorithm. A more up-to-date version
can be found here.

### 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 the range of values, as well as the frequency that values change.

This algorithm is a great little control signal generator that can add a bit of zest to a 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 osc and 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
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.

*<<rline.c>>=*```
#include <math.h>
#define SK_RLINE_PRIV
#include "rline.h"
<<macros>>
<<funcs>>
```

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.

*<<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
```

### Core Struct

The core struct is called `sk_rline`

.

*<<typedefs>>=*`typedef struct sk_rline sk_rline;`

*<<structs>>=*```
struct sk_rline {
<<sk_rline>>
};
```

### 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.

*<<sk_rline>>=*`SKFLT rngscale;`

*<<set_random_scaler>>=*`rl->rngscale = 1.0 / ((1L<<31) - 1);`

The current state of the random number generator is stored
as an integer `rng`

. It is initialized to be `seed`

.

*<<sk_rline>>=*`int rng;`

*<<init>>=*```
rl->rng = seed;
<<set_random_scaler>>
<<generate_initial_values>>
```

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.

*<<macros>>=*```
#define SK_RLINE_PHSLEN 0x1000000L
#define SK_RLINE_PHSMSK 0xFFFFFFL
```

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.

*<<sk_rline>>=*`SKFLT maxlens;`

*<<init>>=*`rl->maxlens = (SKFLT)SK_RLINE_PHSLEN / sr;`

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.

*<<sk_rline>>=*```
unsigned long phasepos;
SKFLT scale;
```

*<<init>>=*`rl->phasepos = 0;`

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.

*<<calculate_initial_scale>>=*`rl->scale = (rl->end - rl->start) / SK_RLINE_PHSLEN;`

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.

*<<sk_rline>>=*```
SKFLT start;
SKFLT end;
```

*<<generate_initial_values>>=*```
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>>
```

### Linear Congruential Generator

An internal 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.

*<<macros>>=*`#define LCG(y) (y * 0x343fd + 0x269ec3)`

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.

*<<macros>>=*`#define RNG(y) ((y >> 1) & 0x7fffffff)`

### 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.

*<<funcdefs>>=*`void sk_rline_init(sk_rline *rl, int sr, int seed);`

*<<funcs>>=*```
void sk_rline_init(sk_rline *rl, int sr, int seed)
{
<<init>>
}
```

### Parameters

#### Minimum value

Set with `sk_rline_min`

.

*<<funcdefs>>=*`void sk_rline_min(sk_rline *rl, SKFLT min);`

*<<funcs>>=*```
void sk_rline_min(sk_rline *rl, SKFLT min)
{
rl->min = min;
}
```

*<<sk_rline>>=*`SKFLT min;`

Initialized to be 0.

*<<init>>=*`sk_rline_min(rl, 0);`

#### Maximum value

Set with `sk_rline_max`

.

*<<funcdefs>>=*`void sk_rline_max(sk_rline *rl, SKFLT max);`

*<<funcs>>=*```
void sk_rline_max(sk_rline *rl, SKFLT max)
{
rl->max= max;
}
```

*<<sk_rline>>=*`SKFLT max;`

Initialized to be 1.

*<<init>>=*`sk_rline_max(rl, 1);`

#### Rate

Set with `sk_rline_rate`

.

*<<funcdefs>>=*`void sk_rline_rate(sk_rline *rl, SKFLT rate);`

*<<funcs>>=*```
void sk_rline_rate(sk_rline *rl, SKFLT rate)
{
rl->rate= rate;
}
```

*<<sk_rline>>=*`SKFLT rate;`

Initialized to be 1.

*<<init>>=*`sk_rline_rate(rl, 1);`

### Computing a sample

A single sample is computed with `sk_rline_tick`

.

*<<funcdefs>>=*`SKFLT sk_rline_tick(sk_rline *rl);`

*<<funcs>>=*```
SKFLT sk_rline_tick(sk_rline *rl)
{
SKFLT out;
out = 0;
<<compute_current_sample>>
<<update_phase>>
<<generate_next_line_segment>>
return out;
}
```

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$.

*<<compute_current_sample>>=*```
out = rl->start + rl->phasepos*rl->scale;
out = out * (rl->max - rl->min) + rl->min;
```

Update phase position. The phase is updated by incrementing it by a amount obtained by multilying 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 osc.

*<<update_phase>>=*`rl->phasepos += floor(rl->rate * rl->maxlens);`

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 costly arithmetic computatoin compared to a multiply.

*<<generate_next_line_segment>>=*```
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;
}
```