1 #include "memoryspace.hpp"
2 #include "memorysearch.hpp"
5 #include "serialization.hpp"
9 memory_search::memory_search(memory_space
& space
) throw(std::bad_alloc
)
18 typedef uint8_t value_type
;
19 bool operator()(uint8_t oldv
, uint8_t newv
) const throw() { return true; }
26 search_value(T v
) throw() { val
= v
; }
27 bool operator()(T oldv
, T newv
) const throw() { return (newv
== val
); }
32 struct search_difference
35 search_difference(T v
) throw() { val
= v
; }
36 bool operator()(T oldv
, T newv
) const throw() { return ((newv
- oldv
) == val
); }
44 bool operator()(T oldv
, T newv
) const throw() { return (newv
< oldv
); }
51 bool operator()(T oldv
, T newv
) const throw() { return (newv
<= oldv
); }
58 bool operator()(T oldv
, T newv
) const throw() { return (newv
== oldv
); }
65 bool operator()(T oldv
, T newv
) const throw() { return (newv
!= oldv
); }
72 bool operator()(T oldv
, T newv
) const throw() { return (newv
>= oldv
); }
79 bool operator()(T oldv
, T newv
) const throw() { return (newv
> oldv
); }
86 bool operator()(T oldv
, T newv
) const throw()
88 T mask
= (T
)1 << (sizeof(T
) * 8 - 1);
90 return ((diff
& mask
) != (T
)0);
98 bool operator()(T oldv
, T newv
) const throw()
100 T mask
= (T
)1 << (sizeof(T
) * 8 - 1);
101 T diff
= newv
- oldv
;
102 return ((diff
& mask
) != (T
)0) || (diff
== (T
)0);
109 typedef T value_type
;
110 bool operator()(T oldv
, T newv
) const throw()
112 T mask
= (T
)1 << (sizeof(T
) * 8 - 1);
113 T diff
= newv
- oldv
;
114 return ((diff
& mask
) == (T
)0);
121 typedef T value_type
;
122 bool operator()(T oldv
, T newv
) const throw()
124 T mask
= (T
)1 << (sizeof(T
) * 8 - 1);
125 T diff
= newv
- oldv
;
126 return ((diff
& mask
) == (T
)0) && (diff
!= (T
)0);
132 struct search_value_helper
134 typedef typename
T::value_type value_type
;
135 search_value_helper(const T
& v
) throw()
139 bool operator()(const uint8_t* newv
, const uint8_t* oldv
, uint64_t left
, int endian
) const throw()
141 if(left
< sizeof(value_type
))
143 value_type v1
= serialization::read_endian
<value_type
>(oldv
, endian
);
144 value_type v2
= serialization::read_endian
<value_type
>(newv
, endian
);
152 void dq_all_after(uint64_t* still_in
, uint64_t& candidates
, uint64_t size
, uint64_t after
)
154 for(uint64_t i
= after
; i
< size
; i
++) {
155 if((still_in
[i
/ 64] >> (i
% 64)) & 1) {
156 still_in
[i
/ 64] &= ~(1ULL << (i
% 64));
162 inline void dq_entry(uint64_t* still_in
, uint64_t& candidates
, uint64_t i
)
164 if((still_in
[i
/ 64] >> (i
% 64)) & 1) {
165 still_in
[i
/ 64] &= ~(1ULL << (i
% 64));
170 inline uint64_t next_multiple_of_64(uint64_t i
)
172 return (i
+ 64) >> 6 << 6;
175 inline uint64_t prev_multiple_of_64(uint64_t i
)
177 return ((i
- 64) >> 6 << 6) + 63;
181 void search_block_mapped(uint64_t* still_in
, uint64_t& candidates
, memory_space::region
& region
,
182 uint64_t rbase
, uint64_t ibase
, T
& helper
, std::vector
<uint8_t>& previous_content
)
184 if(ibase
>= previous_content
.size())
186 unsigned char* mem
= region
.direct_map
;
187 uint64_t rsize
= region
.size
;
188 int endian
= region
.endian
;
190 uint64_t switch_at
= ibase
+ rsize
- rbase
; //The smallest i not in this region.
191 rsize
= min(rsize
, previous_content
.size() - ibase
);
192 for(unsigned j
= rbase
; j
< rsize
; i
++, j
++) {
193 //Advance blocks of 64 addresses if none of the addresses match.
194 while(still_in
[i
/ 64] == 0 && next_multiple_of_64(i
) <= switch_at
) {
196 i
= next_multiple_of_64(i
);
199 //This might match. Check it.
200 if(!helper(mem
+ j
, &previous_content
[i
], rsize
- j
, endian
))
201 dq_entry(still_in
, candidates
, i
);
206 void search_block_read(uint64_t* still_in
, uint64_t& candidates
, memory_space::region
& region
, uint64_t rbase
,
207 uint64_t ibase
, T
& helper
, std::vector
<uint8_t>& previous_content
)
209 if(ibase
>= previous_content
.size())
211 uint64_t rsize
= region
.size
;
212 int endian
= region
.endian
;
214 uint64_t switch_at
= ibase
+ rsize
- rbase
; //The smallest i not in this region.
217 const size_t buffer_capacity
= 4096;
218 unsigned char buffer
[buffer_capacity
];
219 uint64_t buffer_offset
= 0; //The offset in buffer.
220 uint64_t buffer_remaining
= 0; //Number of bytes remaining in buffer.
221 uint64_t buffer_soffset
= rbase
; //The offset buffer start corresponds to.
222 uint64_t buffer_eoffset
= rbase
; //The first offset not in buffer.
224 rsize
= min(rsize
, previous_content
.size() - ibase
);
225 for(unsigned j
= rbase
; j
< rsize
; i
++, j
++) {
226 //Fill the buffer again if it has gotten low enough.
227 if(buffer_remaining
< 256 && buffer_eoffset
!= rsize
) {
229 memmove(buffer
, buffer
+ buffer_offset
, buffer_remaining
);
231 size_t fill_amount
= min((uint64_t)buffer_capacity
, rsize
- buffer_eoffset
);
232 region
.read(buffer_eoffset
, buffer
+ buffer_remaining
, fill_amount
);
233 buffer_eoffset
+= fill_amount
;
234 buffer_remaining
+= fill_amount
;
236 //Advance blocks of 64 addresses if none of the addresses match.
237 while(still_in
[i
/ 64] == 0 && next_multiple_of_64(i
) <= switch_at
) {
239 i
= next_multiple_of_64(i
);
240 uint64_t advance
= i
- old_i
;
242 buffer_offset
+= advance
;
243 buffer_remaining
-= advance
;
244 buffer_soffset
+= advance
;
246 //This might match. Check it.
247 if(!helper(buffer
+ buffer_offset
, &previous_content
[i
], buffer_remaining
, endian
))
248 dq_entry(still_in
, candidates
, i
);
255 void copy_block_mapped(uint8_t* old
, memory_space::region
& region
, uint64_t rbase
, uint64_t maxr
)
257 memcpy(old
, region
.direct_map
+ rbase
, min(region
.size
- rbase
, maxr
));
260 void copy_block_read(uint8_t* old
, memory_space::region
& region
, uint64_t rbase
, uint64_t maxr
)
262 region
.read(rbase
, old
, min(region
.size
- rbase
, maxr
));
265 void dq_block(uint64_t* still_in
, uint64_t& candidates
, memory_space::region
& region
, uint64_t rbase
,
266 uint64_t ibase
, uint64_t first
, uint64_t last
, uint64_t ramsize
)
270 if(last
< region
.base
+ rbase
|| first
>= region
.base
+ region
.size
)
271 return; //Nothing to DQ in this block.
272 first
= max(first
, region
.base
+ rbase
) - region
.base
+ rbase
;
273 last
= last
- region
.base
- rbase
;
274 last
= min(last
, ramsize
- ibase
);
275 uint64_t ilast
= ibase
+ last
;
276 for(uint64_t i
= ibase
+ first
; i
<= ilast
; i
++) {
277 while(still_in
[i
/ 64] == 0 && next_multiple_of_64(i
) <= ilast
) {
278 i
= next_multiple_of_64(i
);
281 dq_entry(still_in
, candidates
, i
);
285 void candidates_block(std::list
<uint64_t>& out
, memory_space::region
& region
, uint64_t rbase
, uint64_t ibase
,
286 uint64_t* still_in
, uint64_t ramsize
)
290 uint64_t rsize
= region
.size
;
292 uint64_t switch_at
= ibase
+ rsize
- rbase
; //The smallest i not in this region.
293 rsize
= min(rsize
, ramsize
- ibase
);
294 for(unsigned j
= rbase
; j
< rsize
; i
++, j
++) {
295 //Advance blocks of 64 addresses if none of the addresses match.
296 while(still_in
[i
/ 64] == 0 && next_multiple_of_64(i
) <= switch_at
) {
298 i
= next_multiple_of_64(i
);
301 if((still_in
[i
/ 64] >> (i
% 64)) & 1)
302 out
.push_back(region
.base
+ j
);
308 void memory_search::dq_range(uint64_t first
, uint64_t last
)
310 auto t
= mspace
.lookup_linear(0);
314 uint64_t size
= previous_content
.size();
317 t
= mspace
.lookup_linear(i
);
320 dq_all_after(&still_in
[0], candidates
, size
, i
);
323 dq_block(&still_in
[0], candidates
, *t
.first
, t
.second
, i
, first
, last
, previous_content
.size());
324 i
+= t
.first
->size
- t
.second
;
328 template<class T
> void memory_search::search(const T
& obj
) throw()
330 search_value_helper
<T
> helper(obj
);
331 auto t
= mspace
.lookup_linear(0);
334 uint64_t size
= previous_content
.size();
338 t
= mspace
.lookup_linear(i
);
341 dq_all_after(&still_in
[0], candidates
, size
, i
);
344 if(t
.first
->direct_map
) {
345 search_block_mapped(&still_in
[0], candidates
, *t
.first
, t
.second
, i
, helper
,
347 copy_block_mapped(&previous_content
[i
], *t
.first
, t
.second
,
348 max((uint64_t)previous_content
.size(), i
) - i
);
350 search_block_read(&still_in
[0], candidates
, *t
.first
, t
.second
, i
, helper
, previous_content
);
351 copy_block_read(&previous_content
[i
], *t
.first
, t
.second
,
352 max((uint64_t)previous_content
.size(), i
) - i
);
354 i
+= t
.first
->size
- t
.second
;
358 template<typename T
> void memory_search::s_value(T value
) throw() { search(search_value
<T
>(value
)); }
359 template<typename T
> void memory_search::s_difference(T value
) throw() { search(search_difference
<T
>(value
)); }
360 template<typename T
> void memory_search::s_lt() throw() { search(search_lt
<T
>()); }
361 template<typename T
> void memory_search::s_le() throw() { search(search_le
<T
>()); }
362 template<typename T
> void memory_search::s_eq() throw() { search(search_eq
<T
>()); }
363 template<typename T
> void memory_search::s_ne() throw() { search(search_ne
<T
>()); }
364 template<typename T
> void memory_search::s_ge() throw() { search(search_ge
<T
>()); }
365 template<typename T
> void memory_search::s_gt() throw() { search(search_gt
<T
>()); }
366 template<typename T
> void memory_search::s_seqlt() throw() { search(search_seqlt
<T
>()); }
367 template<typename T
> void memory_search::s_seqle() throw() { search(search_seqle
<T
>()); }
368 template<typename T
> void memory_search::s_seqge() throw() { search(search_seqge
<T
>()); }
369 template<typename T
> void memory_search::s_seqgt() throw() { search(search_seqgt
<T
>()); }
371 template<typename T
> T
memory_search::v_read(uint64_t addr
) throw() { return mspace
.read
<T
>(addr
); }
372 template<typename T
> void memory_search::v_write(uint64_t addr
, T val
) throw() { mspace
.write
<T
>(addr
, val
); }
374 template<typename T
> T
memory_search::v_readold(uint64_t addr
) throw()
377 auto t
= mspace
.lookup_linear(0);
380 //Search for linear range containing the address.
382 t
= mspace
.lookup_linear(i
);
385 if(t
.first
->base
<= addr
&& t
.first
->base
+ t
.first
->size
> addr
) {
386 //Global address t.first->base <=> linear address i.
387 uint64_t linaddr
= addr
- t
.first
->base
+ i
;
388 uint64_t maxr
= t
.first
->size
+ t
.first
->base
- addr
;
389 maxr
= min(maxr
, (uint64_t)sizeof(T
));
390 char buf
[sizeof(T
)] = {0};
391 if(previous_content
.size() < linaddr
+ maxr
)
393 memcpy(buf
, &previous_content
[linaddr
], maxr
);
394 return serialization::read_endian
<T
>(buf
, t
.first
->endian
);
396 i
+= t
.first
->size
- t
.second
;
401 template<typename T
> void memorysearch_pull_type(memory_search
& s
)
403 eat_argument(&memory_search::s_value
<T
>);
404 eat_argument(&memory_search::s_difference
<T
>);
405 eat_argument(&memory_search::s_lt
<T
>);
406 eat_argument(&memory_search::s_le
<T
>);
407 eat_argument(&memory_search::s_eq
<T
>);
408 eat_argument(&memory_search::s_ne
<T
>);
409 eat_argument(&memory_search::s_ge
<T
>);
410 eat_argument(&memory_search::s_gt
<T
>);
411 eat_argument(&memory_search::s_seqlt
<T
>);
412 eat_argument(&memory_search::s_seqle
<T
>);
413 eat_argument(&memory_search::s_seqge
<T
>);
414 eat_argument(&memory_search::s_seqgt
<T
>);
415 eat_argument(&memory_search::v_read
<T
>);
416 eat_argument(&memory_search::v_readold
<T
>);
417 eat_argument(&memory_search::v_write
<T
>);
420 template<typename T
> void memorysearch_pull_type2(memory_search
& s
)
422 eat_argument(&memory_search::s_value
<T
>);
423 eat_argument(&memory_search::s_difference
<T
>);
424 eat_argument(&memory_search::s_lt
<T
>);
425 eat_argument(&memory_search::s_le
<T
>);
426 eat_argument(&memory_search::s_eq
<T
>);
427 eat_argument(&memory_search::s_ne
<T
>);
428 eat_argument(&memory_search::s_ge
<T
>);
429 eat_argument(&memory_search::s_gt
<T
>);
430 eat_argument(&memory_search::v_read
<T
>);
431 eat_argument(&memory_search::v_readold
<T
>);
432 eat_argument(&memory_search::v_write
<T
>);
435 void memorysearch_pull_all(memory_search
& s
)
437 memorysearch_pull_type
<int8_t>(s
);
438 memorysearch_pull_type
<uint8_t>(s
);
439 memorysearch_pull_type
<int16_t>(s
);
440 memorysearch_pull_type
<uint16_t>(s
);
441 memorysearch_pull_type
<ss_int24_t
>(s
);
442 memorysearch_pull_type
<ss_uint24_t
>(s
);
443 memorysearch_pull_type
<int32_t>(s
);
444 memorysearch_pull_type
<uint32_t>(s
);
445 memorysearch_pull_type
<int64_t>(s
);
446 memorysearch_pull_type
<uint64_t>(s
);
447 memorysearch_pull_type2
<float>(s
);
448 memorysearch_pull_type2
<double>(s
);
451 void memory_search::update() throw() { search(search_update()); }
453 uint64_t memory_search::get_candidate_count() throw()
458 std::list
<uint64_t> memory_search::get_candidates() throw(std::bad_alloc
)
460 std::list
<uint64_t> out
;
461 auto t
= mspace
.lookup_linear(0);
467 t
= mspace
.lookup_linear(i
);
470 candidates_block(out
, *t
.first
, t
.second
, i
, &still_in
[0], previous_content
.size());
471 i
+= t
.first
->size
- t
.second
;
476 bool memory_search::is_candidate(uint64_t addr
) throw()
478 auto t
= mspace
.lookup_linear(0);
484 t
= mspace
.lookup_linear(i
);
487 if(i
>= previous_content
.size())
489 uint64_t rsize
= t
.first
->size
;
490 rsize
= min(rsize
, previous_content
.size() - i
);
491 if(addr
>= t
.first
->base
+ t
.second
&& addr
< t
.first
->base
+ rsize
) {
492 uint64_t adv
= addr
- (t
.first
->base
+ t
.second
);
493 uint64_t ix
= i
+ adv
;
494 return ((still_in
[ix
/ 64] >> (ix
% 64)) & 1);
496 i
+= t
.first
->size
- t
.second
;
501 uint64_t memory_search::cycle_candidate_vma(uint64_t addr
, bool next
) throw()
503 auto t
= mspace
.lookup_linear(0);
509 t
= mspace
.lookup_linear(i
);
512 if(i
>= previous_content
.size())
514 uint64_t rsize
= t
.first
->size
;
515 int64_t switch_at
= i
+ rsize
- t
.second
; //The smallest i not in this region.
516 rsize
= min(rsize
, previous_content
.size() - i
);
517 if(addr
>= t
.first
->base
+ t
.second
&& addr
< t
.first
->base
+ rsize
) {
518 uint64_t baseaddr
= t
.first
->base
+ t
.second
;
519 int64_t tryoff
= addr
- baseaddr
+ i
;
520 int64_t finoff
= tryoff
;
526 while(tryoff
< finoff
|| !warped
) {
527 if(tryoff
>= switch_at
) {
533 if(still_in
[tryoff
/ 64] == 0)
534 tryoff
= next_multiple_of_64(tryoff
);
536 if((still_in
[tryoff
/ 64] >> (tryoff
% 64)) & 1)
537 return tryoff
- i
+ baseaddr
;
544 while(tryoff
> finoff
|| !warped
) {
546 tryoff
= switch_at
- 1;
551 if(still_in
[tryoff
/ 64] == 0)
552 tryoff
= prev_multiple_of_64(tryoff
);
554 if((still_in
[tryoff
/ 64] >> (tryoff
% 64)) & 1)
555 return tryoff
- i
+ baseaddr
;
561 i
+= t
.first
->size
- t
.second
;
566 void memory_search::reset() throw(std::bad_alloc
)
568 uint64_t linearram
= mspace
.get_linear_size();
569 previous_content
.resize(linearram
);
570 still_in
.resize((linearram
+ 63) / 64);
571 for(uint64_t i
= 0; i
< linearram
/ 64; i
++)
572 still_in
[i
] = 0xFFFFFFFFFFFFFFFFULL
;
574 still_in
[linearram
/ 64] = (1ULL << (linearram
% 64)) - 1;
575 candidates
= linearram
;
577 auto t
= mspace
.lookup_linear(0);
583 t
= mspace
.lookup_linear(i
);
586 if(t
.first
->direct_map
)
587 copy_block_mapped(&previous_content
[i
], *t
.first
, t
.second
,
588 max((uint64_t)previous_content
.size(), i
) - i
);
590 copy_block_read(&previous_content
[i
], *t
.first
, t
.second
,
591 max((uint64_t)previous_content
.size(), i
) - i
);
592 i
+= t
.first
->size
- t
.second
;
597 void memory_search::savestate(std::vector
<char>& buffer
, enum savestate_type type
) const
600 uint64_t linsize
= mspace
.get_linear_size();
601 if(type
== ST_PREVMEM
)
603 else if(type
== ST_SET
)
604 size
= 17 + (linsize
+ 63) / 64 * 8;
605 else if(type
== ST_ALL
)
606 size
= 17 + linsize
+ (linsize
+ 63) / 64 * 8;
608 throw std::runtime_error("Invalid savestate type");
611 serialization::u64b(&buffer
[1], linsize
);
613 if(type
== ST_PREVMEM
|| type
== ST_ALL
) {
614 memcpy(&buffer
[offset
], &previous_content
[0], min(linsize
, (uint64_t)previous_content
.size()));
617 if(type
== ST_SET
|| type
== ST_ALL
) {
618 serialization::u64b(&buffer
[offset
], candidates
);
620 size_t bound
= min((linsize
+ 63) / 64, (uint64_t)still_in
.size());
621 for(unsigned i
= 0; i
< bound
; i
++) {
622 serialization::u64b(&buffer
[offset
], still_in
[i
]);
628 void memory_search::loadstate(const std::vector
<char>& buffer
)
630 if(buffer
.size() < 9 || buffer
[0] < ST_PREVMEM
|| buffer
[0] > ST_ALL
)
631 throw std::runtime_error("Invalid memory search save");
632 uint64_t linsize
= serialization::u64b(&buffer
[1]);
633 if(linsize
!= mspace
.get_linear_size())
634 throw std::runtime_error("Save size mismatch (not from this game)");
635 if(!previous_content
.size())
637 savestate_type type
= (savestate_type
)buffer
[0];
639 if(type
== ST_PREVMEM
|| type
== ST_ALL
) {
640 memcpy(&previous_content
[0], &buffer
[offset
], min(linsize
, (uint64_t)previous_content
.size()));
643 if(type
== ST_SET
|| type
== ST_ALL
) {
644 candidates
= serialization::u64b(&buffer
[offset
]);
646 size_t bound
= min((linsize
+ 63) / 64, (uint64_t)still_in
.size());
647 for(unsigned i
= 0; i
< bound
; i
++) {
648 still_in
[i
] = serialization::u64b(&buffer
[offset
]);