1 // This file is part of Freecell Solver. It is subject to the license terms in
2 // the COPYING.txt file found in the top-level directory of this distribution
3 // and at http://fc-solve.shlomifish.org/docs/distro/COPYING.html . No part of
4 // Freecell Solver, including this file, may be copied, modified, propagated,
5 // or distributed except according to the terms contained in the COPYING file.
6 //
7 // Copyright (c) 2000 Shlomi Fish
8
9 // delta_states.h - header file for common functions to the delta_states
10 // functionality.
11 #pragma once
12
13 #ifdef __cplusplus
14 extern "C" {
15 #endif
16
17 #include "rinutils/bit_rw.h"
18 #include "dbm_common.h"
19
20 #ifdef FCS_DEBONDT_DELTA_STATES
21 #include "var_base_writer.h"
22 #include "var_base_reader.h"
23 #define FCS_ENCODED_STATE_COUNT_CHARS 16
24 #define CARD_ARRAY_LEN ((RANK_KING + 1) * FCS_NUM_SUITS)
25
26 typedef struct
27 {
28 FCS_ON_NOT_FC_ONLY(int sequences_are_built_by;)
29 int num_freecells;
30 size_t num_columns;
31 fcs_state *init_state, *derived_state;
32 size_t bits_per_orig_cards_in_column;
33 int card_states[CARD_ARRAY_LEN];
34 int8_t bakers_dozen_topmost_cards_lookup[((1 << 6) / 8) + 1];
35 fcs_var_base_reader r;
36 fcs_var_base_writer w;
37 } fcs_delta_stater;
38
39 #else
40 #define FCS_ENCODED_STATE_COUNT_CHARS 24
41 typedef struct
42 {
43 FCS_ON_NOT_FC_ONLY(int sequences_are_built_by;)
44 size_t num_freecells;
45 size_t num_columns;
46 fcs_state *init_state, *derived_state;
47 size_t bits_per_orig_cards_in_column;
48 } fcs_delta_stater;
49 #endif
50
fc_solve_delta_stater_set_derived(fcs_delta_stater * const self,fcs_state * const state)51 static inline void fc_solve_delta_stater_set_derived(
52 fcs_delta_stater *const self, fcs_state *const state)
53 {
54 self->derived_state = state;
55 }
56
57 typedef struct
58 {
59 uint8_t s[FCS_ENCODED_STATE_COUNT_CHARS];
60 } fcs_encoded_state_buffer;
61
62 #if SIZEOF_VOID_P == 4
63 #define FCS_EXPLICIT_REFCOUNT 1
64 #endif
65
66 #ifdef FCS_DBM_RECORD_POINTER_REPR
67
68 typedef struct
69 {
70 fcs_encoded_state_buffer key;
71 uintptr_t parent_and_refcount;
72 #ifdef FCS_EXPLICIT_REFCOUNT
73 uint8_t refcount;
74 #endif
75 } fcs_dbm_record;
76
77 #define FCS_DBM_RECORD_SHIFT ((sizeof(rec->parent_and_refcount) - 1) * 8)
78
79 #ifdef FCS_EXPLICIT_REFCOUNT
fcs_dbm_record_get_parent_ptr(fcs_dbm_record * const rec)80 static inline fcs_dbm_record *fcs_dbm_record_get_parent_ptr(
81 fcs_dbm_record *const rec)
82 {
83 return (fcs_dbm_record *)(rec->parent_and_refcount);
84 }
85 #else
fcs_dbm_record_get_parent_ptr(fcs_dbm_record * const rec)86 static inline fcs_dbm_record *fcs_dbm_record_get_parent_ptr(
87 fcs_dbm_record *const rec)
88 {
89 return (fcs_dbm_record *)(rec->parent_and_refcount &
90 (~(((uintptr_t)0xFF) << FCS_DBM_RECORD_SHIFT)));
91 }
92 #endif
93
fcs_dbm_record_set_parent_ptr(fcs_dbm_record * const rec,fcs_dbm_record * const parent_ptr)94 static inline void fcs_dbm_record_set_parent_ptr(
95 fcs_dbm_record *const rec, fcs_dbm_record *const parent_ptr)
96 {
97 rec->parent_and_refcount = ((uintptr_t)parent_ptr);
98 #ifdef FCS_EXPLICIT_REFCOUNT
99 rec->refcount = 0;
100 #endif
101 }
102
103 #ifdef FCS_EXPLICIT_REFCOUNT
fcs_dbm_record_get_refcount(const fcs_dbm_record * const rec)104 static inline uint8_t fcs_dbm_record_get_refcount(
105 const fcs_dbm_record *const rec)
106 {
107 return rec->refcount;
108 }
109 #else
fcs_dbm_record_get_refcount(const fcs_dbm_record * const rec)110 static inline uint8_t fcs_dbm_record_get_refcount(
111 const fcs_dbm_record *const rec)
112 {
113 return (uint8_t)(rec->parent_and_refcount >> FCS_DBM_RECORD_SHIFT);
114 }
115 #endif
116
117 #ifdef FCS_EXPLICIT_REFCOUNT
fcs_dbm_record_set_refcount(fcs_dbm_record * const rec,const uint8_t new_val)118 static inline void fcs_dbm_record_set_refcount(
119 fcs_dbm_record *const rec, const uint8_t new_val)
120 {
121 rec->refcount = new_val;
122 }
123 #else
fcs_dbm_record_set_refcount(fcs_dbm_record * const rec,const uint8_t new_val)124 static inline void fcs_dbm_record_set_refcount(
125 fcs_dbm_record *const rec, const uint8_t new_val)
126 {
127 rec->parent_and_refcount &=
128 (~(((const uintptr_t)0xFF) << FCS_DBM_RECORD_SHIFT));
129 rec->parent_and_refcount |=
130 (((const uintptr_t)new_val) << FCS_DBM_RECORD_SHIFT);
131 }
132 #endif
133
fcs_dbm_record_increment_refcount(fcs_dbm_record * const rec)134 static inline void fcs_dbm_record_increment_refcount(fcs_dbm_record *const rec)
135 {
136 fcs_dbm_record_set_refcount(rec, fcs_dbm_record_get_refcount(rec) + 1);
137 }
138
139 // Returns the new value so we can tell if it is zero.
fcs_dbm_record_decrement_refcount(fcs_dbm_record * const rec)140 static inline uint8_t fcs_dbm_record_decrement_refcount(
141 fcs_dbm_record *const rec)
142 {
143 const uint8_t new_val = fcs_dbm_record_get_refcount(rec) - 1;
144
145 fcs_dbm_record_set_refcount(rec, new_val);
146
147 return new_val;
148 }
149
150 #else
151
152 typedef struct
153 {
154 fcs_encoded_state_buffer key;
155 fcs_encoded_state_buffer parent;
156 } fcs_dbm_record;
157
158 #endif
159
fcs_init_encoded_state(fcs_encoded_state_buffer * enc_state)160 static inline void fcs_init_encoded_state(fcs_encoded_state_buffer *enc_state)
161 {
162 memset(enc_state, '\0', sizeof(*enc_state));
163 }
164
165 #ifdef __cplusplus
166 }
167 #endif
168