bool TransactionFilter::matches(h256 _bloom) const
{
	auto have = [=](Address const& a) { return _bloom.contains(a.bloom()); };
	if (m_from.size())
	{
		for (auto i: m_from)
			if (have(i))
				goto OK1;
		return false;
	}
	OK1:
	if (m_to.size())
	{
		for (auto i: m_to)
			if (have(i))
				goto OK2;
		return false;
	}
	OK2:
	if (m_stateAltered.size() || m_altered.size())
	{
		for (auto i: m_altered)
			if (have(i))
				goto OK3;
		for (auto i: m_stateAltered)
			if (have(i.first) && _bloom.contains(h256(i.second).bloom()))
				goto OK3;
		return false;
	}
	OK3:
	return true;
}

Public dev::recover(Signature const& _sig, h256 const& _message)
{
	Public ret;
#ifdef ETH_HAVE_SECP256K1
	bytes o(65);
	int pubkeylen;
	if (!secp256k1_ecdsa_recover_compact(s_secp256k1, _message.data(), _sig.data(), o.data(), &pubkeylen, false, _sig[64]))
		return Public();
	ret = FixedHash<64>(o.data() + 1, Public::ConstructFromPointer);
#else
	ret = s_secp256k1pp.recover(_sig, _message.ref());
#endif
	if (ret == c_zeroKey)
		return Public();
	return ret;
}

Public dev::recover(Signature const& _sig, h256 const& _message)
{
    int v = _sig[64];
    if (v > 3)
        return {};

    auto* ctx = getCtx();
    secp256k1_ecdsa_recoverable_signature rawSig;
    if (!secp256k1_ecdsa_recoverable_signature_parse_compact(ctx, &rawSig, _sig.data(), v))
        return {};

    secp256k1_pubkey rawPubkey;
    if (!secp256k1_ecdsa_recover(ctx, &rawPubkey, &rawSig, _message.data()))
        return {};

    std::array<byte, 65> serializedPubkey;
    size_t serializedPubkeySize = serializedPubkey.size();
    secp256k1_ec_pubkey_serialize(
            ctx, serializedPubkey.data(), &serializedPubkeySize,
            &rawPubkey, SECP256K1_EC_UNCOMPRESSED
    );
    assert(serializedPubkeySize == serializedPubkey.size());
    // Expect single byte header of value 0x04 -- uncompressed public key.
    assert(serializedPubkey[0] == 0x04);
    // Create the Public skipping the header.
    return Public{&serializedPubkey[1], Public::ConstructFromPointer};
}

std::string OverlayDB::lookup(h256 const& _h) const
{
	std::string ret = MemoryDB::lookup(_h);
	if (ret.empty() && m_db)
		m_db->Get(m_readOptions, ldb::Slice((char const*)_h.data(), 32), &ret);
	return ret;
}

inline void update(_T& _sha, h256 const& _value)
{
    int i = 0;
    byte const* data = _value.data();
    for (; i != 32 && data[i] == 0; ++i);
    _sha.Update(data + i, 32 - i);
}

EthashProofOfWork::Result EthashAux::LightAllocation::compute(h256 const& _headerHash, Nonce const& _nonce) const
{
	ethash_return_value r = ethash_light_compute(light, *(ethash_h256_t*)_headerHash.data(), (uint64_t)(u64)_nonce);
	if (!r.success)
		BOOST_THROW_EXCEPTION(DAGCreationFailure());
	return EthashProofOfWork::Result{h256((uint8_t*)&r.result, h256::ConstructFromPointer), h256((uint8_t*)&r.mix_hash, h256::ConstructFromPointer)};
}

bool OverlayDB::exists(h256 const& _h) const
{
	if (MemoryDB::exists(_h))
		return true;
	std::string ret;
	if (m_db)
		m_db->Get(m_readOptions, ldb::Slice((char const*)_h.data(), 32), &ret);
	return !ret.empty();
}

bool dev::verify(Public const& _p, Signature const& _s, h256 const& _hash)
{
	if (!_p)
		return false;
#ifdef ETH_HAVE_SECP256K1
	return _p == recover(_s, _hash);
#else
	return s_secp256k1pp.verify(_p, _s, _hash.ref(), true);
#endif
}

bool OverlayDB::deepkill(h256 const& _h)
{
	// kill in memoryDB
	kill(_h);

	//kill in overlayDB
	ldb::Status s = m_db->Delete(m_writeOptions, ldb::Slice((char const*)_h.data(), 32));
	if (s.ok())
		return true;
	else
		return false;
}

Signature dev::sign(Secret const& _k, h256 const& _hash)
{
#ifdef ETH_HAVE_SECP256K1
	Signature s;
	int v;
	if (!secp256k1_ecdsa_sign_compact(s_secp256k1, _hash.data(), s.data(), _k.data(), NULL, NULL, &v))
		return Signature();
	s[64] = v;
	return s;
#else
	return s_secp256k1pp.sign(_k, _hash);
#endif
}

bool dev::verify(PublicCompressed const& _key, h512 const& _signature, h256 const& _hash)
{
    auto* ctx = getCtx();

    secp256k1_ecdsa_signature rawSig;
    if (!secp256k1_ecdsa_signature_parse_compact(ctx, &rawSig, _signature.data()))
        return false;

    secp256k1_pubkey rawPubkey;
    if (!secp256k1_ec_pubkey_parse(ctx, &rawPubkey, _key.data(), PublicCompressed::size))
        return false;  // Invalid public key.

    return secp256k1_ecdsa_verify(ctx, &rawSig, _hash.data(), &rawPubkey);
}

 string fromRaw(h256 _n)
 {
     if (_n)
     {
         string s((char const *)_n.data(), 32);
         auto l = s.find_first_of('\0');
         if (!l)
             return "";
         if (l != string::npos)
             s.resize(l);
         for (auto i: s)
             if (i < 32)
                 return "";
         return s;
     }
     return "";
 }

void OverlayDB::kill(h256 const& _h)
{
#if ELE_PARANOIA || 1
	if (!MemoryDB::kill(_h))
	{
		std::string ret;
		if (m_db)
			m_db->Get(m_readOptions, ldb::Slice((char const*)_h.data(), 32), &ret);
		// No point node ref decreasing for EmptyTrie since we never bother incrementing it in the first place for
		// empty storage tries.
		if (ret.empty() && _h != EmptyTrie)
			cnote << "Decreasing DB node ref count below zero with no DB node. Probably have a corrupt Trie." << _h;

		// TODO: for 1.1: ref-counted triedb.
	}
#else
	MemoryDB::kill(_h);
#endif
}

Signature dev::sign(Secret const& _k, h256 const& _hash)
{
    auto* ctx = getCtx();
    secp256k1_ecdsa_recoverable_signature rawSig;
    if (!secp256k1_ecdsa_sign_recoverable(ctx, &rawSig, _hash.data(), _k.data(), nullptr, nullptr))
        return {};

    Signature s;
    int v = 0;
    secp256k1_ecdsa_recoverable_signature_serialize_compact(ctx, s.data(), &v, &rawSig);

    SignatureStruct& ss = *reinterpret_cast<SignatureStruct*>(&s);
    ss.v = static_cast<byte>(v);
    if (ss.s > c_secp256k1n / 2)
    {
        ss.v = static_cast<byte>(ss.v ^ 1);
        ss.s = h256(c_secp256k1n - u256(ss.s));
    }
    assert(ss.s <= c_secp256k1n / 2);
    return s;
}

OverlayDB State::openDB(std::string const& _basePath, h256 const& _genesisHash, WithExisting _we)
{
	std::string path = _basePath.empty() ? Defaults::get()->m_dbPath : _basePath;

	if (_we == WithExisting::Kill)
	{
		cnote << "Killing state database (WithExisting::Kill).";
		boost::filesystem::remove_all(path + "/state");
	}

	path += "/" + toHex(_genesisHash.ref().cropped(0, 4)) + "/" + toString(c_databaseVersion);
	boost::filesystem::create_directories(path);
	DEV_IGNORE_EXCEPTIONS(fs::permissions(path, fs::owner_all));

	ldb::Options o;
	o.max_open_files = 256;
	o.create_if_missing = true;
	ldb::DB* db = nullptr;
	ldb::Status status = ldb::DB::Open(o, path + "/state", &db);
	if (!status.ok() || !db)
	{
		if (boost::filesystem::space(path + "/state").available < 1024)
		{
			cwarn << "Not enough available space found on hard drive. Please free some up and then re-run. Bailing.";
			BOOST_THROW_EXCEPTION(NotEnoughAvailableSpace());
		}
		else
		{
			cwarn << status.ToString();
			cwarn <<
				"Database " <<
				(path + "/state") <<
				"already open. You appear to have another instance of ethereum running. Bailing.";
			BOOST_THROW_EXCEPTION(DatabaseAlreadyOpen());
		}
	}

	cnote << "Opened state DB.";
	return OverlayDB(db);
}

Signature Secp256k1PP::sign(Secret const& _key, h256 const& _hash)
{
	// assumption made by signing alogrithm
	assert(m_q == m_qs);
	
	Signature sig;
	
	Integer k(kdf(_key, _hash).data(), 32);
	if (k == 0)
		BOOST_THROW_EXCEPTION(InvalidState());
	k = 1 + (k % (m_qs - 1));
	
	ECP::Point rp;
	Integer r;
	{
		Guard l(x_params);
		rp = m_params.ExponentiateBase(k);
		r = m_params.ConvertElementToInteger(rp);
	}
	sig[64] = 0;
//	sig[64] = (r >= m_q) ? 2 : 0;
	
	Integer kInv = k.InverseMod(m_q);
	Integer z(_hash.asBytes().data(), 32);
	Integer s = (kInv * (Integer(_key.data(), 32) * r + z)) % m_q;
	if (r == 0 || s == 0)
		BOOST_THROW_EXCEPTION(InvalidState());
	
//	if (s > m_qs)
//	{
//		s = m_q - s;
//		if (sig[64])
//			sig[64] ^= 1;
//	}
	
	sig[64] |= rp.y.IsOdd() ? 1 : 0;
	r.Encode(sig.data(), 32);
	s.Encode(sig.data() + 32, 32);
	return sig;
}

static std::string minHex(h256 const& _h)
{
	unsigned i = 0;
	for (; i < 31 && !_h[i]; ++i) {}
	return toHex(_h.ref().cropped(i));
}