14#include "utils/uuid.h"
27#include <unordered_set>
39void sha1_block(uint32_t h[5],
const unsigned char *block)
42 for (
int i = 0; i < 16; ++i)
43 w[i] = (
static_cast<uint32_t
>(block[4*i]) << 24) |
44 (
static_cast<uint32_t
>(block[4*i + 1]) << 16) |
45 (
static_cast<uint32_t
>(block[4*i + 2]) << 8) |
46 static_cast<uint32_t
>(block[4*i + 3]);
47 for (
int i = 16; i < 80; ++i) {
48 const uint32_t v = w[i-3] ^ w[i-8] ^ w[i-14] ^ w[i-16];
49 w[i] = (v << 1) | (v >> 31);
51 uint32_t a = h[0], b = h[1], c = h[2], d = h[3], e = h[4];
52 for (
int i = 0; i < 80; ++i) {
55 f = (b & c) | (~b & d);
61 f = (b & c) | (b & d) | (c & d);
67 const uint32_t tmp = ((a << 5) | (a >> 27)) + f + e + k + w[i];
70 c = (b << 30) | (b >> 2);
74 h[0] += a; h[1] += b; h[2] += c; h[3] += d; h[4] += e;
77void sha1(
const unsigned char *data, std::size_t len,
unsigned char out[20])
89 static const uint32_t init[5] = {0x67452301u, 0xEFCDAB89u, 0x98BADCFEu,
90 0x10325476u, 0xC3D2E1F0u};
91 std::copy(init, init + 5, ctx->
h);
97 const unsigned char *data,
size_t len)
101 const std::size_t take = std::min(len,
sizeof(ctx->
block) - ctx->
used);
102 std::copy(data, data + take, ctx->
block + ctx->
used);
108 sha1_block(ctx->
h, ctx->
block);
111 for (; len >=
sizeof(ctx->
block); data += 64, len -= 64)
112 sha1_block(ctx->
h, data);
113 std::copy(data, data + len, ctx->
block);
118 unsigned char out[20])
120 const uint64_t bits = ctx->
len * 8;
121 unsigned char pad[72] = {0x80};
123 const std::size_t npad = (ctx->
used < 56 ? 56 : 120) - ctx->
used;
124 for (
int i = 0; i < 8; ++i)
125 pad[npad + i] =
static_cast<unsigned char>(bits >> (8 * (7 - i)));
127 for (
int i = 0; i < 5; ++i) {
128 out[4*i] =
static_cast<unsigned char>(ctx->
h[i] >> 24);
129 out[4*i + 1] =
static_cast<unsigned char>(ctx->
h[i] >> 16);
130 out[4*i + 2] =
static_cast<unsigned char>(ctx->
h[i] >> 8);
131 out[4*i + 3] =
static_cast<unsigned char>(ctx->
h[i]);
136 unsigned char out[20])
138 sha1(data, len, out);
144 static const unsigned char ns[16] = {
145 0x92, 0x0d, 0x4f, 0x02, 0x87, 0x18, 0x53, 0x19,
146 0x95, 0x32, 0xd4, 0xab, 0x83, 0xa6, 0x44, 0x89
148 std::vector<unsigned char> data(16 + name.size());
149 std::copy(ns, ns + 16, data.begin());
150 std::copy(name.begin(), name.end(), data.begin() + 16);
151 unsigned char digest[20];
152 sha1(data.data(), data.size(), digest);
154 std::copy(digest, digest + 16, u.
data);
155 u.
data[6] =
static_cast<unsigned char>((u.
data[6] & 0x0F) | 0x50);
156 u.
data[8] =
static_cast<unsigned char>((u.
data[8] & 0x3F) | 0x80);
163 std::unordered_map<gate_t, pg_uuid_t, hash_gate_t> uuid_of;
167 static std::unordered_set<std::string> created;
168 constexpr std::size_t kCreatedCap = 4u << 20;
169 if (created.size() > kCreatedCap)
172 bool have_one =
false;
174 const auto ensureOne = [&]() {
184 const std::vector<pg_uuid_t> &children,
187 if (!created.insert(key).second)
194 static_cast<unsigned>(children.size()),
195 children.empty() ? NULL : children.
data(),
199 std::vector<gate_t> stack(roots);
200 while (!stack.empty()) {
201 CHECK_FOR_INTERRUPTS();
202 const gate_t g = stack.back();
203 if (uuid_of.find(g) != uuid_of.end()) {
211 const std::string tok = dd.
getUUID(g);
212 if (!tok.empty() && tok[0] ==
'\x01') {
226 double existing = 0.;
230 "probability %g, not the %g this compilation "
231 "needs: two distinct coins hashed to one gate",
245 for (
const auto &c : dd.
getWires(g))
246 if (uuid_of.find(c) == uuid_of.end()) {
262 createOnce(token,
gate_monus, {one, child},
false);
277 }
else if (wires.size() == 1) {
278 token = uuid_of[wires[0]];
280 std::vector<std::string> texts;
281 texts.reserve(wires.size());
282 for (
const auto &c : wires)
284 std::sort(texts.begin(), texts.end());
286 for (std::size_t i = 0; i < texts.size(); ++i) {
293 std::vector<pg_uuid_t> children;
294 children.reserve(wires.size());
295 for (
const auto &c : wires)
296 children.push_back(uuid_of[c]);
298 children, certified);
304 provsql_error(
"materializeCertifiedDD: unsupported gate type");
305 throw std::runtime_error(
"unreachable");
323 for (
const auto &r : roots) {
328 const auto it = uuid_of.find(r);
329 if (it != uuid_of.end())
330 it->second =
wrapRoute(it->second, route);
338 static std::unordered_set<std::string> created;
339 constexpr std::size_t kCreatedCap = 1u << 20;
340 if (created.size() > kCreatedCap)
348 false, 0, 0, text.c_str());
354 static std::unordered_set<std::string> created;
355 constexpr std::size_t kCreatedCap = 1u << 20;
356 if (created.size() > kCreatedCap)
Boolean provenance circuit with support for knowledge compilation.
constexpr unsigned DNNF_CERT_INFO
d-DNNF certificate value for the (gate-type-specific) per-gate info field.
@ NOT
Logical negation of a single child gate.
@ OR
Logical disjunction of child gates.
@ AND
Logical conjunction of child gates.
@ IN
Input (variable) gate representing a base tuple.
@ MULIN
Multivalued-input gate (one of several options).
pg_uuid_t wrapRoute(const pg_uuid_t &child, provsql_route route)
Wrap a materialised root in a transparent annotation naming the route that produced it,...
std::unordered_map< gate_t, pg_uuid_t, hash_gate_t > materializeCertifiedDD(const dDNNF &dd, const std::vector< gate_t > &roots, provsql_route route)
Materialise (the reachable part of) a certified d-D into the mmap store.
void provsql_sha1(const unsigned char *data, size_t len, unsigned char out[20])
SHA-1 of len bytes of data (RFC 3174).
pg_uuid_t wrapAssumedAbsorptive(const pg_uuid_t &child)
Wrap a materialised root in the 'absorptive' assumption marker and return the wrapper's UUID.
pg_uuid_t provsqlUuidV5(const std::string &name)
RFC 4122 version-5 UUID in the ProvSQL namespace.
void provsql_sha1_final(provsql_sha1_ctx *ctx, unsigned char out[20])
The SHA-1 of all the bytes given to ctx.
void provsql_sha1_init(provsql_sha1_ctx *ctx)
Start an incremental SHA-1.
void provsql_sha1_update(provsql_sha1_ctx *ctx, const unsigned char *data, size_t len)
Hash len more bytes of data.
Content-addressed materialisation of a certified d-D into the mmap provenance store.
gate_t
Strongly-typed gate identifier.
bool isDNNFCertified(gate_t g) const
Is gate g certified by the d-DNNF per-gate marking?
double getProb(gate_t g) const
Return the probability stored for gate g.
std::vector< gate_t > & getWires(gate_t g)
Return a mutable reference to the child-wire list of gate g.
gateType getGateType(gate_t g) const
Return the type of gate g.
uuid getUUID(gate_t g) const
Return the UUID string associated with gate g.
A d-DNNF circuit supporting exact probabilistic and game-theoretic evaluation.
#define provsql_error(fmt,...)
Report a fatal ProvSQL error and abort the current transaction.
void provsql_internal_create_gate(const pg_uuid_t *token, gate_type type, unsigned nb_children, const pg_uuid_t *children_data)
Internal entry point behind create_gate(): cache + worker IPC.
void provsql_internal_create_gate_with(const pg_uuid_t *token, gate_type type, unsigned nb_children, const pg_uuid_t *children, bool has_infos, unsigned info1, unsigned info2, const char *extra)
Create a gate together with its infos and its text, in one message that is not answered.
provsql_set_prob_result provsql_internal_set_prob(const pg_uuid_t *token, double prob, double *existing)
Write a gate's probability from in-extension C/C++ code.
Background worker and IPC primitives for mmap-backed circuit storage.
@ PROVSQL_SET_PROB_ALREADY_SET
Holds a different value; refused.
Core types, constants, and utilities shared across ProvSQL.
#define PROVSQL_GATE_ZERO_UUID
UUID of the semiring zero gate: the result of the SQL function gate_zero(), created with the extensio...
#define PROVSQL_GATE_ONE_UUID
UUID of the semiring one gate, the result of gate_one().
@ gate_annotation
Transparent single-child wrapper carrying a query-level annotation in extra (inversion-free certifica...
@ gate_assumed
Structural marker over a single child whose sub-circuit was computed under a Boolean-provenance assum...
provsql_route
Tags identifying the planner-time route that produced a circuit.
@ PROVSQL_ROUTE_NONE
No route rewrite: ordinary lineage.
@ PROVSQL_ROUTE_REACHABILITY
Recursive-reachability compiler (src/reachability_evaluate.cpp).
static const char * provsql_route_name(provsql_route route)
The name of a route, as the probability dispatcher reports it and as the annotation wrapper of a mate...
pg_uuid_t string2uuid(const string &source)
Parse a UUID string into a pg_uuid_t.
string uuid2string(pg_uuid_t uuid)
Format a pg_uuid_t as a std::string.
C++ utility functions for UUID manipulation.
The state of an incremental SHA-1: the digest of a text given in pieces, without holding it whole (th...
uint64_t len
Bytes hashed so far.
unsigned char block[64]
The bytes not yet hashed, short of a block.
size_t used
How many of block are used.