1// Copyright 2009-2021 Intel Corporation
2// SPDX-License-Identifier: Apache-2.0
3
4#pragma once
5
6// input: importance in 'cdf'
7// output: cdf of importance in 'cdf'
8//         return sum
9uniform float Distribution1D_create(
10    const uniform int size, uniform float *uniform cdf);
11
12struct Sample1D
13{
14  int idx; // relative sample index to start
15  float frac; // relative prosition of the random sample inside
16              // the selected bin (useful for random sample re-using)
17  float pdf; // the pdf of sampling the position idx+frac
18             // when frac is sampled uniformly inside the idx^th bin
19  float prob; // the probability of sampling the idx^th bin
20};
21
22inline Sample1D Distribution1D_sample(const uniform int size,
23    const uniform float *uniform cdf,
24    // we may sample different rows within one gang: use a varying offset
25    // 'start' instead of a varying pointer 'cdf'
26    const int start,
27    const float s)
28{
29  // find minimum index where cdf[i-1] <= s < cdf[i]
30  int first = start;
31  int len = size;
32
33  while (len > 0) {
34    const int half = len >> 1;
35    const int mid = first + half;
36    if (s < cdf[mid]) {
37      len = half;
38    } else {
39      first = mid + 1;
40      len -= half + 1;
41    }
42  }
43
44  Sample1D ret;
45  ret.idx = first - start;
46  const float bef = first == start ? 0.0f : cdf[first - 1];
47  const float dpdf = cdf[first] - bef;
48  ret.prob = dpdf;
49  ret.pdf = dpdf * size;
50  ret.frac = (s - bef) * rcp(dpdf); // rescale
51
52  return ret;
53}
54